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;
#define int long long
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
int fx[100005] , n , m;
vector<int> adj[100005] ;
vector<pii> radj[100005];
vector<int> p[100005];
bool cmp(int i , int j){
if(fx[i] == fx[j]) return i;
else{
return fx[i] > fx[j];
}
}
int32_t main(){
scanf("%lld%lld" , &n , &m);
vector<pii> edges;
for(int i = 0 ; i < m ; i++){
int x, y,z;
cin>>x>>y>>z;
x--, y--;
p[x].pb(z);
adj[x].pb(y);
edges.pb(pii(x,y));
}
for(int i = 0 ; i < n;i++) sort(p[i].begin() , p[i].end()), fx[i] = (int) 1e18;
for(int i =0;i<m;i++){
radj[edges[i].S].pb(pii(p[edges[i].F][0] , edges[i].F));
}
priority_queue<pii , vector<pii> , greater<pii> > pq;
fx[n-1] = 0;
pq.push(pii(0 , n-1));
while(!pq.empty()){
pii u = pq.top();
pq.pop();
if(fx[u.S] != u.F) continue;
for(int j = 0 ; j < radj[u.S].size(); j++){
pii v = radj[u.S][j];
if(fx[v.S] > v.F + u.F){
fx[v.S] = v.F + u.F;
pq.push(pii(fx[v.S] , v.S));
}
}
}
for(int i = 0 ; i < n;i++){
sort(adj[i].begin() , adj[i].end() , cmp);
}
for(int i = 0 ; i < n; i++) fx[i] = (int) 1e18;
fx[0] = 0;
pq.push(pii(0 , 0));
while(!pq.empty()){
pii u = pq.top();
pq.pop();
if(fx[u.S] != u.F) continue;
for(int j = 0 ; j < adj[u.S].size() ;j++){
pii v = pii(p[u.S][j] , adj[u.S][j]);
if(fx[v.S] > v.F + u.F){
fx[v.S] = v.F + u.F;
pq.push(pii(fx[v.S] , v.S));
}
}
}
printf("%lld\n" , fx[n-1]);
}
Compilation message (stderr)
ferries.cpp: In function 'int32_t main()':
ferries.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < radj[u.S].size(); j++){
^
ferries.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < adj[u.S].size() ;j++){
^
ferries.cpp:22:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld" , &n , &m);
^
# | 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... |