제출 #1084157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084157		I_FloPPed21	Robot (JOI21_ho_t4)	C++14	100 / 100	787 ms	89020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct muchie
{
    int to,p;
    long long c;
};
map<int,vector<muchie>>adj[200005];
long long dp[200005];
map<int,long long>dp2[100005],sum[100005];
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        dp[i]=1e18;
    dp[1]=0;
    for(int i=1; i<=m; i++)
    {
        int a,b,p;
        long long c;
        cin>>a>>b>>p>>c;
        adj[a][p].push_back({b,p,c});
        adj[b][p].push_back({a,p,c});
        sum[a][p]+=c;
        sum[b][p]+=c;
    }
    priority_queue<pair<long long,pair<int,int>>>pq;
    pq.push({0,{1,0}});
    while(!pq.empty())
    {
        int nod,p;
        long long c;
        nod=pq.top().second.first,c=pq.top().first,p=pq.top().second.second;
        pq.pop();
        if(p!=0)
        {
            if(-c!=dp2[nod][p])
                continue;
            for(muchie u:adj[nod][p])
            {
                long long cost=sum[nod][p]-u.c-c;
                if(cost<dp[u.to])
                {
                    dp[u.to]=cost;
                    pq.push({-dp[u.to],{u.to,0}});
                }
            }
        }
        else
        {
            if(-c!=dp[nod])
                continue;
            for(auto &u :adj[nod])
            {
                for(auto k :u.second)
                {
                    int p=k.p;
                    long long caz1=sum[nod][p]-k.c;
                    if(caz1-c<dp[k.to])
                    {
                        dp[k.to]=caz1-c;
                        pq.push({-dp[k.to],{k.to,0}});
                    }
                    long long caz2=k.c-c;
                    if(caz2<dp[k.to])
                    {
                        dp[k.to]=caz2;
                        pq.push({-dp[k.to],{k.to,0}});
                    }

                    long long caz3=-c;
                    if(!dp2[k.to].count(p) || caz3<dp2[k.to][p])
                    {
                        dp2[k.to][p]=caz3;
                        pq.push({-dp2[k.to][p],{k.to,p}});
                    }
                }
            }
        }
    }
    if(dp[n]==1e18)
        cout<<-1<<'\n';
    else
        cout<<dp[n]<<'\n';
    return 0;
}

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