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 int lli;
typedef pair<lli,lli> pii;
vector<vector<pii> > adj;
void dijk(int start,vector<lli>& dist,vector<lli>& pre){
set<pii> nodes;
int len=dist.size();
dist=vector<lli>(len,1e17);
nodes.insert(pii(0,start));
dist[start]=0;
pre=vector<lli>(len,-1);
while(!nodes.empty())
{
auto sim=*nodes.begin();
nodes.erase(sim);
for(auto u:adj[sim.second]){
if(dist[sim.second]+u.second<dist[u.first]){
if(nodes.find(pii(dist[u.first],u.first))!=nodes.end())
nodes.erase(pii(dist[u.first],u.first));
dist[u.first]=dist[sim.second]+u.second;
pre[u.first]=sim.second;
nodes.insert(pii(dist[u.first],u.first));
}
}
}
}
/*
5 7
1 3
1 5
1 2 1
2 3 3
1 3 2
3 4 1
3 5 2
1 4 1
1 5 7
* */
int main(){
int n,m;
cin>>n>>m;
lli s,t,u,v;
cin>>s>>t>>u>>v;
adj=vector<vector<pii> >(n+1,vector<pii>());
for (int i = 0; i < m; i++)
{
int a,b,c;
cin>>a>>b>>c;
adj[a].push_back(pii(b,c));
adj[b].push_back(pii(a,c));
}
vector<lli> distS(n+1),preS(n+1);
dijk(s,distS,preS);
vector<lli> distv(n+1),prev(n+1);
dijk(v,distv,prev);
lli snc=1e17;
for (int i = t; i != -1 ; i=preS[i])
{
//cout <<"i: "<<i<<"\n";
snc=min(distv[i],snc);
}
cout << snc<<"\n";
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... |