| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 89993 | thebes | Ferries (NOI13_ferries) | C++14 | 0 ms | 0 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 i, x, y, dist[MN], idx[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 ferries(int N,int M,int *A,int *B,int *C){
for(i=0;i<M;i++){
adj[B[i]].push_back(A[i]);
w[A[i]].push_back(C[i]);
}
for(i=1;i<=N;i++) sort(w[i].begin(),w[i].end(),[](int i,int j){return i>j;});
memset(dist,-1,sizeof(dist));
q.push({N,0});
while(q.size()){
auto v=q.top(); q.pop();
if(dist[v.first]!=-1) continue;
else dist[v.first]=v.second;
for(auto e : adj[v.first]){
if(dist[e]==-1){
int W = w[e][idx[e]]; idx[e]++;
q.push({e, W+v.second});
}
}
}
return dist[1];
}