#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()
{
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.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
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()
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
385 ms |
30204 KB |
Output is correct |
2 |
Correct |
448 ms |
22744 KB |
Output is correct |
3 |
Correct |
440 ms |
24496 KB |
Output is correct |
4 |
Correct |
386 ms |
23264 KB |
Output is correct |
5 |
Correct |
460 ms |
24276 KB |
Output is correct |
6 |
Correct |
416 ms |
30844 KB |
Output is correct |
7 |
Correct |
446 ms |
23140 KB |
Output is correct |
8 |
Correct |
476 ms |
23836 KB |
Output is correct |
9 |
Correct |
421 ms |
24340 KB |
Output is correct |
10 |
Correct |
352 ms |
27180 KB |
Output is correct |
11 |
Correct |
148 ms |
15816 KB |
Output is correct |
12 |
Correct |
437 ms |
27972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
460 ms |
24052 KB |
Output is correct |
2 |
Correct |
449 ms |
23272 KB |
Output is correct |
3 |
Correct |
458 ms |
27996 KB |
Output is correct |
4 |
Correct |
439 ms |
24504 KB |
Output is correct |
5 |
Correct |
467 ms |
23756 KB |
Output is correct |
6 |
Correct |
443 ms |
23944 KB |
Output is correct |
7 |
Correct |
489 ms |
29524 KB |
Output is correct |
8 |
Correct |
486 ms |
23700 KB |
Output is correct |
9 |
Correct |
458 ms |
23756 KB |
Output is correct |
10 |
Correct |
462 ms |
23956 KB |
Output is correct |
11 |
Correct |
181 ms |
13772 KB |
Output is correct |
12 |
Correct |
468 ms |
26616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
3932 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
31 ms |
5232 KB |
Output is correct |
5 |
Correct |
17 ms |
3872 KB |
Output is correct |
6 |
Correct |
2 ms |
2396 KB |
Output is correct |
7 |
Incorrect |
3 ms |
2652 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
385 ms |
30204 KB |
Output is correct |
2 |
Correct |
448 ms |
22744 KB |
Output is correct |
3 |
Correct |
440 ms |
24496 KB |
Output is correct |
4 |
Correct |
386 ms |
23264 KB |
Output is correct |
5 |
Correct |
460 ms |
24276 KB |
Output is correct |
6 |
Correct |
416 ms |
30844 KB |
Output is correct |
7 |
Correct |
446 ms |
23140 KB |
Output is correct |
8 |
Correct |
476 ms |
23836 KB |
Output is correct |
9 |
Correct |
421 ms |
24340 KB |
Output is correct |
10 |
Correct |
352 ms |
27180 KB |
Output is correct |
11 |
Correct |
148 ms |
15816 KB |
Output is correct |
12 |
Correct |
437 ms |
27972 KB |
Output is correct |
13 |
Correct |
460 ms |
24052 KB |
Output is correct |
14 |
Correct |
449 ms |
23272 KB |
Output is correct |
15 |
Correct |
458 ms |
27996 KB |
Output is correct |
16 |
Correct |
439 ms |
24504 KB |
Output is correct |
17 |
Correct |
467 ms |
23756 KB |
Output is correct |
18 |
Correct |
443 ms |
23944 KB |
Output is correct |
19 |
Correct |
489 ms |
29524 KB |
Output is correct |
20 |
Correct |
486 ms |
23700 KB |
Output is correct |
21 |
Correct |
458 ms |
23756 KB |
Output is correct |
22 |
Correct |
462 ms |
23956 KB |
Output is correct |
23 |
Correct |
181 ms |
13772 KB |
Output is correct |
24 |
Correct |
468 ms |
26616 KB |
Output is correct |
25 |
Correct |
15 ms |
3932 KB |
Output is correct |
26 |
Correct |
1 ms |
2396 KB |
Output is correct |
27 |
Correct |
1 ms |
2396 KB |
Output is correct |
28 |
Correct |
31 ms |
5232 KB |
Output is correct |
29 |
Correct |
17 ms |
3872 KB |
Output is correct |
30 |
Correct |
2 ms |
2396 KB |
Output is correct |
31 |
Incorrect |
3 ms |
2652 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |