Submission #1023279

#TimeUsernameProblemLanguageResultExecution timeMemory
1023279KhoaDuyRobot (JOI21_ho_t4)C++14
100 / 100
954 ms120056 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' struct node{ int u,c,w; }; struct cmp{ bool operator()(node &a,node &b){ return (a.w>b.w); } }; struct edge{ int v,c,p; }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; vector<map<int,int>> bst(n+1); vector<map<int,vector<edge>>> graph(n+1); vector<map<int,int>> Pre(n+1); vector<map<int,bool>> vis(n+1); for(int i=0;i<m;i++){ int a,b,c,p; cin >> a >> b >> c >> p; graph[a][c].push_back({b,c,p}); graph[b][c].push_back({a,c,p}); Pre[a][c]+=p; Pre[b][c]+=p; } priority_queue<node,vector<node>,cmp> pq; bst[1][0]=0; pq.push({1,0,0}); while(!pq.empty()){ node curr=pq.top(); pq.pop(); if(bst[curr.u][curr.c]<curr.w||vis[curr.u][curr.c]){ continue; } vis[curr.u][curr.c]=true; if(curr.c){ for(edge x:graph[curr.u][curr.c]){ int dist=curr.w+Pre[curr.u][curr.c]-x.p; if(bst[x.v].find(0)==bst[x.v].end()||bst[x.v][0]>dist){ bst[x.v][0]=dist; pq.push({x.v,0,dist}); } } } else{ for(pair<const int,vector<edge>> temp:graph[curr.u]){ for(edge x:temp.second){ int dist=curr.w+min(x.p,Pre[curr.u][x.c]-x.p); if(bst[x.v].find(0)==bst[x.v].end()||bst[x.v][0]>dist){ bst[x.v][0]=dist; pq.push({x.v,0,dist}); } dist=curr.w; if(bst[x.v].find(x.c)==bst[x.v].end()||bst[x.v][x.c]>dist){ bst[x.v][x.c]=dist; pq.push({x.v,x.c,dist}); } } } } } if(bst[n].find(0)==bst[n].end()){ cout << -1; } else{ cout << bst[n][0]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...