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;
using ll = long long;
#define MAXN (1000005)
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll N,M;
cin>>N>>M;
vector<pair<ll,ll> > fromzero[N];
vector<pair<ll,ll> > fromn[N];
for(ll i = 0;i < M;i++){
ll a,b,c;
cin>>a>>b>>c;
a--;
b--;
fromzero[a].push_back(make_pair(c,b));
fromn[b].push_back(make_pair(c,a));
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
ll distfromzero[N];
ll distfromn[N];
memset(distfromzero,-1,sizeof(distfromzero));
memset(distfromn,-1,sizeof(distfromn));
pq.push(make_pair(0,N - 1));
distfromn[N - 1] = 0;
while(!pq.empty()){
pair<ll,ll> u = pq.top();
pq.pop();
if(u.first != distfromn[u.second]){
continue;
}
for(auto a : fromn[u.second]){
if(distfromn[a.second] == -1 || distfromn[a.second] > u.first + a.first){
distfromn[a.second] = u.first + a.first;
pq.push(make_pair(distfromn[a.second],a.second));
}
}
}
pq.push(make_pair(0,0));
distfromzero[0] = 0;
while(!pq.empty()){
pair<ll,ll> u = pq.top();
pq.pop();
if(u.first != distfromzero[u.second]){
continue;
}
vector<ll> v;
for(auto a : fromzero[u.second]){
v.push_back(a.first);
}
vector<pair<ll,ll> > nodes;
for(auto a : fromzero[u.second]){
nodes.push_back(make_pair(distfromzero[u.second] + distfromn[a.second],a.second));
}
sort(v.begin(),v.end(),greater<ll>());
sort(nodes.begin(),nodes.end());
ll index = 0;
for(auto a : nodes){
if(distfromzero[a.second] == -1 || distfromzero[a.second] > u.first + v[index]){
distfromzero[a.second] = u.first + v[index];
pq.push(make_pair(distfromzero[a.second],a.second));
index++;
}
}
}
ll sum = 0;
for(ll i = 0;i < N;i++){
sum = max(sum,distfromzero[i] + distfromn[i]);
}
cout<<sum<<'\n';
}
# | 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... |