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 INT_MAX LLONG_MAX
int mx[2][100001];
int mx2[2][100001];
struct node
{
int pos,we;
node (int a,int b)
{
pos=a;
we=b;
}
};
struct node2
{
int pos,we,rwe,st,type;
node2 (int a,int b,int c,int d,int e)
{
pos=a;
we=b;
rwe=c;
st=d;
type=e;
}
};
bool cmp2(node2 x,node2 y)
{
return x.we>y.we;
}
bool cmp(node x,node y)
{
return x.we>y.we;
}
void dij(int type,int st,vector<vector<pair<int,int>>> &v)
{
priority_queue<node,vector<node>,function<bool(node,node)>> p(cmp);
p.push({st,0});
mx[type][st]=0;
while (p.empty()==false)
{
node tmp=p.top();p.pop();
if (tmp.we!=mx[type][tmp.pos]) continue;
for (auto it:v[tmp.pos])
{
if (it.second+tmp.we<mx[type][it.first])
{
mx[type][it.first]=it.second+tmp.we;
p.push({it.first,mx[type][it.first]});
}
}
}
}
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("TEST.INP","r",stdin);
//freopen("TEST.OUT","w",stdout);
int n,m;
cin>>n>>m;
int s,t;
cin>>s>>t;
int u,v;
cin>>u>>v;
vector<vector<pair<int,int>>> V(n+1);
for (int i=0;i<m;i++)
{
int x,y,w;
cin>>x>>y>>w;
V[x].push_back({y,w});
V[y].push_back({x,w});
}
for (int i=1;i<=n;i++)
{
mx2[1][i]=mx2[0][i]=mx[1][i]=mx[0][i]=INT_MAX;
}
dij(1,s,V);
dij(0,t,V);
priority_queue<node2,vector<node2>,function<bool(node2,node2)>> pr(cmp2);
pr.push({u,0,0,0,1});
pr.push({u,0,0,u,0});
mx2[0][u]=0;
mx2[1][u]=0;
while (pr.empty()==false)
{
node2 tmp=pr.top();pr.pop();
if (tmp.type&&tmp.we!=mx2[tmp.type][tmp.pos]) continue;
else if (!tmp.st&&tmp.we!=mx2[tmp.type][tmp.pos]) continue;
for (auto it:V[tmp.pos])
{
node2 tt=tmp;
if (tt.type)
{
if (tt.we+it.second<mx2[tt.type][it.first])
{
mx2[tt.type][it.first]=tt.we+it.second;
pr.push({it.first,tt.we+it.second,0,0,tt.type});
}
if (it.second+mx[1][tmp.pos]+mx[0][it.first]==mx[1][t]||it.second+mx[0][tmp.pos]+mx[1][it.first]==mx[1][t])
{
tt.type=0;
tt.st=tt.pos;
tt.rwe=it.second;
if (tt.we<mx2[tt.type][it.first])
{
mx2[tt.type][it.first]=tt.we;
pr.push({it.first,tt.we,tt.rwe,tt.st,tt.type});
}
}
}
else
{
if (tt.we+it.second<mx2[tt.type][it.first])
{
mx2[tt.type][it.first]=tt.we+it.second;
pr.push({it.first,tt.we+it.second,0,0,tt.type});
}
if ((it.second+tt.rwe+mx[1][tt.st]+mx[0][it.first]==mx[1][t]||it.second+tt.rwe+mx[1][it.first]+mx[0][tt.st]==mx[1][t])&&tt.st)
{
if (tmp.we<mx2[tmp.type][it.first])
{
mx2[tmp.type][it.first]=tt.we;
pr.push({it.first,tt.we,tt.rwe+it.second,tt.st,tt.type});
}
}
}
}
}
cout<<min(mx2[0][v],mx2[1][v]);
}
Compilation message (stderr)
commuter_pass.cpp:5: warning: "INT_MAX" redefined
5 | #define INT_MAX LLONG_MAX
|
In file included from /usr/include/c++/10/climits:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
from commuter_pass.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:120: note: this is the location of the previous definition
120 | #define INT_MAX __INT_MAX__
|
commuter_pass.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
56 | main()
| ^~~~
# | 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... |