Submission #974834

#	Time	Username	Problem	Language	Result	Execution time	Memory
974834		imarn	Robot (JOI21_ho_t4)	C++14	100 / 100	960 ms	84684 KiB

Main

#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define sz(x) (ll)x.size()
#define pp pair<int,pii>
using namespace std;
const int mxn=1e5+5;
map<int,vector<pair<int,ll>>>g[mxn];
map<int,ll>tt[mxn],dp[mxn];
ll d[mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);ll ans=0;
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c,p;cin>>a>>b>>c>>p;
        g[a][c].pb({b,p});g[b][c].pb({a,p});
        tt[a][c]+=p;tt[b][c]+=p;dp[a][c]=dp[b][c]=1e16;
    }for(int i=1;i<=n;i++)d[i]=1e16;d[1]=0;
    priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>>pq;
    pq.push({0,{1,0}});
    while(!pq.empty()){
        auto u=pq.top();pq.pop();
        if(u.s.s==0&&u.f>d[u.s.f])continue;
        if(u.s.s!=0&&u.f>dp[u.s.f][u.s.s])continue;
        if(u.s.s==0){
            for(auto it:g[u.s.f]){
                for(auto v:it.s){
                    if(dp[v.f][it.f]>u.f)dp[v.f][it.f]=u.f,pq.push({u.f,{v.f,it.f}});
                    if(d[v.f]>u.f+min(v.s,tt[u.s.f][it.f]-v.s)){
                        d[v.f]=u.f+min(v.s,tt[u.s.f][it.f]-v.s);pq.push({d[v.f],{v.f,0}});
                    }
                }
            }
        }
        else {
            for(auto v : g[u.s.f][u.s.s]){
                if(d[v.f]>u.f+tt[u.s.f][u.s.s]-v.s)d[v.f]=u.f+tt[u.s.f][u.s.s]-v.s,pq.push({d[v.f],{v.f,0}});
            }
        }
    }cout<<(d[n]==1e16?-1:d[n]);

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:15:48: warning: unused variable 'ans' [-Wunused-variable]
   15 |     ios_base::sync_with_stdio(0);cin.tie(0);ll ans=0;
      |                                                ^~~

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