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 ll long long
#define ff first
#define ss second
const ll N = 1e5+7;
ll pos[4],dis[4][N],n,m;
vector<vector<pair<ll,ll>>> a;
void dijkstra(ll p)
{
priority_queue<pair<ll,ll>> pq;
pq.push({0,pos[p]});
for(ll i = 0;i < n;i++)dis[p][i] = 1e18;
while(!pq.empty())
{
pair<ll,ll> v = pq.top();
pq.pop();
v.ff *= -1;
if(v.ff >= dis[p][v.ss])continue;
dis[p][v.ss] = v.ff;
for(auto x : a[v.ss])pq.push(make_pair(-(v.ff + x.ff),x.ss));
}
return ;
}
ll in[N];
void check(ll p)
{
for(ll i = 0;i < n;i++)in[i] = 0;
queue<ll> q;
q.push(p);
in[p] = 1;
while(!q.empty())
{
ll v = q.front();
q.pop();
for(auto x : a[v])
{
if(dis[1][v] < dis[1][x.ss] && dis[0][x.ss] + dis[1][x.ss] == dis[1][pos[0]] && !in[x.ss])
{
in[x.ss] = 1;
q.push(x.ss);
}
}
}
}
ll dismin[N];
void getmin(ll s)
{
queue<pair<ll,ll>> q;
q.push(make_pair(dis[2][pos[s]],pos[s]));
while(!q.empty())
{
pair<ll,ll> v = q.front();
q.pop();
v.ff = min(v.ff,dis[2][v.ss]);
dismin[v.ss] = min(dismin[v.ss],v.ff);
for(auto x : a[v.ss])if(in[x.ss] && dis[s][x.ss] > dis[s][v.ss])q.push(make_pair(v.ff,x.ss));
}
return ;
}
int main()
{
cin>>n>>m;
cin>>pos[0]>>pos[1]>>pos[2]>>pos[3];
pos[0]--;pos[1]--;pos[2]--;pos[3]--;
a.resize(n);
for(ll i = 0;i < m;i++)
{
ll x,y,z;
cin>>x>>y>>z;x--;y--;
a[x].push_back(make_pair(z,y));
a[y].push_back(make_pair(z,x));
}
for(ll i = 0;i < n;i++)dismin[i] = 1e18;
dijkstra(0);dijkstra(1);dijkstra(2);dijkstra(3);
check(pos[1]);
//getmin(0);
//getmin(1);
ll ans = dis[2][pos[3]];
for(ll i = 0;i < n;i++)if(in[i])ans = min(dismin[i] + dis[3][i],ans);
cout<<ans;
return 0;
}
# | 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... |