Submission #1083995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083995		I_FloPPed21	Robot (JOI21_ho_t4)	C++17	0 / 100	3069 ms	533344 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+1;
const int M=2e5+1;
int n,m;
map<int,int>mp[N];
vector<pair<int,pair<int,int>>>adj[N];
long long dp[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    dp[i]=1e18;
    for(int i=1; i<=m; i++)
    {
        int a,b,color,c;
        cin>>a>>b>>color>>c;
        adj[a].push_back({b,{color,c}});
        adj[b].push_back({a,{color,c}});
        mp[a][color]+=c;
        mp[b][color]+=c;
    }
    dp[1]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,1});
    while(!pq.empty())
    {
        int cost=-pq.top().first;
        int nod=pq.top().second;
        pq.pop();
        for(auto u:adj[nod])
        {
            int cost1=u.second.second;
            int cost2=mp[nod][u.second.first]-cost1;
            cost1=min(cost1,cost2);

            if(dp[u.first]>cost1+dp[nod])
            {
                dp[u.first]=cost1+dp[nod];
                pq.push({-dp[u.first],u.first});
            }

        }
    }

    if(dp[n]==1e18)
    {
        cout<<-1<<'\n';
        return 0;
    }
    cout<<dp[n]<<'\n';

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:13: warning: unused variable 'cost' [-Wunused-variable]
   29 |         int cost=-pq.top().first;
      |             ^~~~

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42