# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
89995 | thebes | Ferries (NOI13_ferries) | C++14 | 388 ms | 32976 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5+5;
int N, M, i, x, y, W, dist[MN], idx[MN], vis[MN];
vector<int> adj[MN], w[MN];
typedef pair<int,int> pii;
struct pq{bool operator()(const pii&i,const pii&j){return i.second>j.second;}};
priority_queue<pii,vector<pii>,pq> q;
int main(){
for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
scanf("%d%d%d",&x,&y,&W);
adj[y].push_back(x);
w[x].push_back(W);
}
for(i=1;i<=N;i++) sort(w[i].begin(),w[i].end(),[](int i,int j){return i>j;});
memset(dist,0x3f,sizeof(dist));
q.push({N,0});
while(q.size()){
auto v=q.top(); q.pop();
if(vis[v.first]) continue;
else dist[v.first]=v.second,vis[v.first]=1;
for(auto e : adj[v.first]){
W = w[e][idx[e]];
if(!vis[e]&&W+v.second<dist[e]){
idx[e]++;
q.push({e, W+v.second});
}
}
}
printf("%d\n",dist[1]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |