Submission #10375

#TimeUsernameProblemLanguageResultExecution timeMemory
10375gs14004Ferries (NOI13_ferries)C++98
40 / 40
288 ms15888 KiB
#include <cstdio> #include <queue> #include <vector> #include <utility> using namespace std; typedef pair<int,int> pi; priority_queue<int> len[100005]; vector<int> graph[100005]; priority_queue<pi,vector<pi>,greater<pi> > pq; int n,m,v[100005]; int main(){ scanf("%d %d",&n,&m); for (int i=0; i<m; i++) { int p,q,r; scanf("%d %d %d",&p,&q,&r); graph[q].push_back(p); len[p].push(r); } pq.push(pi(0,n)); while (!pq.empty()) { pi x = pq.top(); pq.pop(); if(x.second == 1){ printf("%d",x.first); break; } if(v[x.second]) continue; v[x.second] = 1; for (int i=0; i<graph[x.second].size(); i++) { int pos = graph[x.second][i]; if(v[pos]) continue; int newlen = len[pos].top(); len[pos].pop(); pq.push(pi(newlen + x.first,pos)); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...