#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 200004
#define INF 1e16
using namespace std;
ll n,m,s,t,u,v;
ll d[N][4];
vector < pi > graph[N];
vector < ll > par[N][4];
vector < ll > dag[N];
bool vis[N];
ll minvalue[N];
bool in_path(ll x)
{
return (d[x][0]+d[x][1]==d[t][0]);
}
void dijkstra(int root,int id)
{
rep(i,0,n+1)
{
d[i][id] = INF;
par[i][id].clear();
}
priority_queue < pi > pq;
pq.push(mp(0,root));
d[root][id] = 0;
while(!pq.empty())
{
pi cur = pq.top();
pq.pop();
cur.first*=-1;
if(d[cur.second][id] < cur.first)
continue;
rep(i,0,graph[cur.second].size())
{
ll vv = graph[cur.second][i].first;
ll cc = graph[cur.second][i].second;
if(d[vv][id] > cur.first+cc)
{
d[vv][id]=cur.first+cc;
par[vv][id].clear();
pq.push(mp(-d[vv][id],vv));
}
if(d[vv][id]==cur.first+cc)
par[vv][id].push_back(cur.second);
}
}
return;
}
void construct_dag(ll id)
{
rep(i,1,n+1)
{
rep(j,0,par[i][id].size())
{
dag[i].push_back(par[i][id][j]);
}
}
return;
}
ll solve(ll cur)
{
if(!in_path(cur))
minvalue[cur] = INF;
if(vis[cur] || !in_path(cur))
return INF;
vis[cur]=true;
ll res = d[cur][2] + d[cur][3];
minvalue[cur]=d[cur][3];
rep(i,0,dag[cur].size())
{
ll vv = dag[cur][i];
res = min(res,solve(vv));
minvalue[cur] = min(minvalue[cur],minvalue[vv]);
}
res=min(res,d[cur][2]+minvalue[cur]);
//cout << cur << " "<< res << " " << minvalue[cur] << endl;
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
rep(i,0,m)
{
ll a,b,c;
cin >> a >> b >> c;
graph[a].push_back(mp(b,c));
graph[b].push_back(mp(a,c));
}
dijkstra(s,0);
construct_dag(0);
dijkstra(t,1);
dijkstra(u,2);
dijkstra(v,3);
ll ans = d[u][3];
rep(x,1,n+1)
ans = min(ans,solve(x));
rep(i,1,n+1)
vis[i]=false;
dijkstra(u,3);
dijkstra(v,2);
// cout << endl << endl << endl;
rep(x,1,n+1)
ans = min(ans,solve(x));
cout << ans << endl;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
commuter_pass.cpp:54:13:
rep(i,0,graph[cur.second].size())
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:54:9: note: in expansion of macro 'rep'
rep(i,0,graph[cur.second].size())
^~~
commuter_pass.cpp: In function 'void construct_dag(long long int)':
commuter_pass.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
commuter_pass.cpp:77:13:
rep(j,0,par[i][id].size())
~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:77:9: note: in expansion of macro 'rep'
rep(j,0,par[i][id].size())
^~~
commuter_pass.cpp: In function 'long long int solve(long long int)':
commuter_pass.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
commuter_pass.cpp:98:9:
rep(i,0,dag[cur].size())
~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:98:5: note: in expansion of macro 'rep'
rep(i,0,dag[cur].size())
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
726 ms |
63680 KB |
Output is correct |
2 |
Correct |
784 ms |
62620 KB |
Output is correct |
3 |
Correct |
783 ms |
63576 KB |
Output is correct |
4 |
Correct |
780 ms |
64988 KB |
Output is correct |
5 |
Correct |
808 ms |
63744 KB |
Output is correct |
6 |
Correct |
725 ms |
63524 KB |
Output is correct |
7 |
Correct |
794 ms |
62644 KB |
Output is correct |
8 |
Correct |
803 ms |
62776 KB |
Output is correct |
9 |
Correct |
732 ms |
62092 KB |
Output is correct |
10 |
Correct |
642 ms |
62296 KB |
Output is correct |
11 |
Correct |
358 ms |
55872 KB |
Output is correct |
12 |
Correct |
713 ms |
62268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
750 ms |
63920 KB |
Output is correct |
2 |
Correct |
770 ms |
64012 KB |
Output is correct |
3 |
Correct |
760 ms |
64528 KB |
Output is correct |
4 |
Correct |
781 ms |
65040 KB |
Output is correct |
5 |
Correct |
800 ms |
64816 KB |
Output is correct |
6 |
Correct |
754 ms |
65960 KB |
Output is correct |
7 |
Correct |
795 ms |
64500 KB |
Output is correct |
8 |
Correct |
796 ms |
63528 KB |
Output is correct |
9 |
Correct |
784 ms |
64788 KB |
Output is correct |
10 |
Correct |
825 ms |
64144 KB |
Output is correct |
11 |
Correct |
383 ms |
57824 KB |
Output is correct |
12 |
Correct |
773 ms |
65812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
31096 KB |
Output is correct |
2 |
Correct |
23 ms |
28672 KB |
Output is correct |
3 |
Correct |
21 ms |
28672 KB |
Output is correct |
4 |
Correct |
41 ms |
33528 KB |
Output is correct |
5 |
Correct |
37 ms |
30208 KB |
Output is correct |
6 |
Correct |
21 ms |
28672 KB |
Output is correct |
7 |
Correct |
22 ms |
28800 KB |
Output is correct |
8 |
Correct |
23 ms |
28868 KB |
Output is correct |
9 |
Correct |
22 ms |
28800 KB |
Output is correct |
10 |
Correct |
37 ms |
30456 KB |
Output is correct |
11 |
Correct |
23 ms |
28672 KB |
Output is correct |
12 |
Correct |
22 ms |
28672 KB |
Output is correct |
13 |
Correct |
21 ms |
28672 KB |
Output is correct |
14 |
Correct |
21 ms |
28672 KB |
Output is correct |
15 |
Correct |
21 ms |
28672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
726 ms |
63680 KB |
Output is correct |
2 |
Correct |
784 ms |
62620 KB |
Output is correct |
3 |
Correct |
783 ms |
63576 KB |
Output is correct |
4 |
Correct |
780 ms |
64988 KB |
Output is correct |
5 |
Correct |
808 ms |
63744 KB |
Output is correct |
6 |
Correct |
725 ms |
63524 KB |
Output is correct |
7 |
Correct |
794 ms |
62644 KB |
Output is correct |
8 |
Correct |
803 ms |
62776 KB |
Output is correct |
9 |
Correct |
732 ms |
62092 KB |
Output is correct |
10 |
Correct |
642 ms |
62296 KB |
Output is correct |
11 |
Correct |
358 ms |
55872 KB |
Output is correct |
12 |
Correct |
713 ms |
62268 KB |
Output is correct |
13 |
Correct |
750 ms |
63920 KB |
Output is correct |
14 |
Correct |
770 ms |
64012 KB |
Output is correct |
15 |
Correct |
760 ms |
64528 KB |
Output is correct |
16 |
Correct |
781 ms |
65040 KB |
Output is correct |
17 |
Correct |
800 ms |
64816 KB |
Output is correct |
18 |
Correct |
754 ms |
65960 KB |
Output is correct |
19 |
Correct |
795 ms |
64500 KB |
Output is correct |
20 |
Correct |
796 ms |
63528 KB |
Output is correct |
21 |
Correct |
784 ms |
64788 KB |
Output is correct |
22 |
Correct |
825 ms |
64144 KB |
Output is correct |
23 |
Correct |
383 ms |
57824 KB |
Output is correct |
24 |
Correct |
773 ms |
65812 KB |
Output is correct |
25 |
Correct |
33 ms |
31096 KB |
Output is correct |
26 |
Correct |
23 ms |
28672 KB |
Output is correct |
27 |
Correct |
21 ms |
28672 KB |
Output is correct |
28 |
Correct |
41 ms |
33528 KB |
Output is correct |
29 |
Correct |
37 ms |
30208 KB |
Output is correct |
30 |
Correct |
21 ms |
28672 KB |
Output is correct |
31 |
Correct |
22 ms |
28800 KB |
Output is correct |
32 |
Correct |
23 ms |
28868 KB |
Output is correct |
33 |
Correct |
22 ms |
28800 KB |
Output is correct |
34 |
Correct |
37 ms |
30456 KB |
Output is correct |
35 |
Correct |
23 ms |
28672 KB |
Output is correct |
36 |
Correct |
22 ms |
28672 KB |
Output is correct |
37 |
Correct |
21 ms |
28672 KB |
Output is correct |
38 |
Correct |
21 ms |
28672 KB |
Output is correct |
39 |
Correct |
21 ms |
28672 KB |
Output is correct |
40 |
Correct |
623 ms |
65608 KB |
Output is correct |
41 |
Correct |
722 ms |
64716 KB |
Output is correct |
42 |
Correct |
717 ms |
64524 KB |
Output is correct |
43 |
Correct |
390 ms |
57080 KB |
Output is correct |
44 |
Correct |
393 ms |
57464 KB |
Output is correct |
45 |
Correct |
815 ms |
65556 KB |
Output is correct |
46 |
Correct |
837 ms |
66404 KB |
Output is correct |
47 |
Correct |
824 ms |
66120 KB |
Output is correct |
48 |
Correct |
385 ms |
55416 KB |
Output is correct |
49 |
Correct |
700 ms |
68224 KB |
Output is correct |
50 |
Correct |
799 ms |
64532 KB |
Output is correct |
51 |
Correct |
781 ms |
65260 KB |
Output is correct |