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;
typedef long long ll;
const int mx=1e5+9;
const ll inf=1e18;
ll dist[4][mx+9];
vector<pair<int,ll>>adj[mx];
int n,m,s,t,u,v;
ll dp[2][mx];ll l;
void dikjstra(int node,int cnt)
{
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater < pair<ll,int> >>q;
for(int i=0; i<=n; i++)
{
dist[cnt][i]=inf;
}
q.push({0,node});
dist[cnt][node]=0;
while(!q.empty())
{
pair<ll,int>me=q.top();
q.pop();
int x=me.second;
ll cost=me.first;
for(auto it:adj[x])
{
int node2=it.first;
if(cost+it.second<dist[cnt][it.first])
{ ll cost2=cost+it.second;
dist[cnt][it.first]=cost2;
q.push({(cost2),node2});
}
}
}
}
void dikjstra2(int node,int cnt)
{
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater < pair<ll,int> >>q;
bool vis[n];
for(int i=0; i<=n; i++)
{
// dist[cnt][i]=inf;
vis[i]=0;
}
q.push({0,node});
while(!q.empty())
{
pair<ll,int>me=q.top();
q.pop();
int x=me.second;
if(vis[x]){
continue;
}
vis[x]=1;
ll cost=me.first;
dp[cnt][x]=min(dist[3][x],dp[cnt][x]);
for(auto it:adj[x])
{
int node2=it.first;
if(cost+it.second<=dist[cnt][it.first])
{
dp[cnt][node2]=min( dp[cnt][node2],dp[cnt][x]);
ll cost2=cost+it.second;
q.push({(cost2),node2});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin>>n>>m>>s>>t>>u>>v;
for(int i=0; i<m; i++)
{
ll x,y,c;
cin>>x>>y>>c;
adj[x].push_back({y,c});
adj[y].push_back({x,c});
}
dikjstra(v,3);
dikjstra(u,2);
dikjstra(s,0);
dikjstra(t,1);
l=dist[0][t];
for(int i=1; i<=n; i++)
{
dp[0][i]=dp[1][i]=inf;
}
dikjstra2(t,1);
dikjstra2(s,0);
ll ans=inf;
for(int i=1; i<=n; i++)
{
if(dist[0][i]+dist[1][i]==l)
{
ans=min(dist[2][i]+dp[0][i],ans);
ans=min(dist[2][i]+dp[1][i],ans);
}
}
ans=min(ans,dist[2][v]);
cout<<ans;
}
# | 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... |