#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
priority_queue <pii, vector <pii>, greater <pii>> q;
queue <int> qq;
ll dis[5][N],mn = oo * oo,dp[2][N],ans = oo * oo;
int a,b,c,d,deg[N];
vector <pll> g[N];
vector <int> ng[N];
void calc (int s, int i){
q.push({0,s});
memset(dis[i],0x3f,sizeof dis[i]);
dis[i][s] = 0;
while (!q.empty()){
pii u = q.top();
q.pop();
if (u.st > dis[i][u.nd])
continue;
for (pii v : g[u.nd])
if (v.nd + u.st < dis[i][v.st])
dis[i][v.st] = v.nd + u.st, q.push({dis[i][v.st],v.st});
}
if (i == 1)
mn = dis[i][a];
}
void finalcalc(){
qq.push(a);
//memset (dp,0x3f,sizeof dp);
while (!qq.empty()){
int u = qq.front();
qq.pop();
ans = min (ans,min(dp[0][u] + dis[3][u],dp[1][u] + dis[2][u]));
//cout << u << " " << dp[0][u] << " " << dp[1][u] << "\n";
for (int v : ng[u]){
dp[0][v] = min (dp[0][v],dp[0][u]);
dp[1][v] = min (dp[1][v],dp[1][u]);
deg[v]--;
if (deg[v] == 0)
qq.push(v);
}
}
}
int n,m,u,v,w,i;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
cin >> a >> b >> c >> d;
forr (i,1,m){
cin >> u >> v >> w;
g[u].pb({v,w});
g[v].pb({u,w});
}
calc(a,0);
calc(b,1);
calc(c,2);
calc(d,3);
forr (i,1,n){
//cout << i << " " << dis[0][i] << "\n";
for (pii v : g[i])
if (dis[0][v.st] + v.nd + dis[1][i] == mn)
ng[v.st].pb(i),deg[i]++;
dp[0][i] = dis[2][i];
dp[1][i] = dis[3][i];
}
finalcalc();
cout << min(ans,dis[2][d]);
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
215 ms |
32964 KB |
Output is correct |
2 |
Correct |
214 ms |
32600 KB |
Output is correct |
3 |
Correct |
259 ms |
34048 KB |
Output is correct |
4 |
Correct |
191 ms |
32708 KB |
Output is correct |
5 |
Correct |
206 ms |
33360 KB |
Output is correct |
6 |
Correct |
229 ms |
32708 KB |
Output is correct |
7 |
Correct |
219 ms |
33652 KB |
Output is correct |
8 |
Correct |
245 ms |
33372 KB |
Output is correct |
9 |
Correct |
174 ms |
32452 KB |
Output is correct |
10 |
Correct |
173 ms |
36604 KB |
Output is correct |
11 |
Correct |
82 ms |
29264 KB |
Output is correct |
12 |
Correct |
210 ms |
36804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
32708 KB |
Output is correct |
2 |
Correct |
231 ms |
32576 KB |
Output is correct |
3 |
Correct |
188 ms |
32452 KB |
Output is correct |
4 |
Correct |
248 ms |
32904 KB |
Output is correct |
5 |
Correct |
247 ms |
32820 KB |
Output is correct |
6 |
Correct |
223 ms |
33548 KB |
Output is correct |
7 |
Correct |
235 ms |
33732 KB |
Output is correct |
8 |
Correct |
241 ms |
32712 KB |
Output is correct |
9 |
Correct |
253 ms |
32804 KB |
Output is correct |
10 |
Correct |
258 ms |
32528 KB |
Output is correct |
11 |
Correct |
68 ms |
27984 KB |
Output is correct |
12 |
Correct |
198 ms |
37312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
22360 KB |
Output is correct |
2 |
Correct |
4 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21080 KB |
Output is correct |
4 |
Correct |
14 ms |
24408 KB |
Output is correct |
5 |
Correct |
9 ms |
22872 KB |
Output is correct |
6 |
Correct |
5 ms |
21080 KB |
Output is correct |
7 |
Correct |
4 ms |
21336 KB |
Output is correct |
8 |
Correct |
5 ms |
21332 KB |
Output is correct |
9 |
Correct |
5 ms |
21080 KB |
Output is correct |
10 |
Correct |
9 ms |
22684 KB |
Output is correct |
11 |
Correct |
4 ms |
21080 KB |
Output is correct |
12 |
Correct |
4 ms |
21084 KB |
Output is correct |
13 |
Correct |
4 ms |
21080 KB |
Output is correct |
14 |
Correct |
4 ms |
21084 KB |
Output is correct |
15 |
Correct |
5 ms |
21080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
215 ms |
32964 KB |
Output is correct |
2 |
Correct |
214 ms |
32600 KB |
Output is correct |
3 |
Correct |
259 ms |
34048 KB |
Output is correct |
4 |
Correct |
191 ms |
32708 KB |
Output is correct |
5 |
Correct |
206 ms |
33360 KB |
Output is correct |
6 |
Correct |
229 ms |
32708 KB |
Output is correct |
7 |
Correct |
219 ms |
33652 KB |
Output is correct |
8 |
Correct |
245 ms |
33372 KB |
Output is correct |
9 |
Correct |
174 ms |
32452 KB |
Output is correct |
10 |
Correct |
173 ms |
36604 KB |
Output is correct |
11 |
Correct |
82 ms |
29264 KB |
Output is correct |
12 |
Correct |
210 ms |
36804 KB |
Output is correct |
13 |
Correct |
226 ms |
32708 KB |
Output is correct |
14 |
Correct |
231 ms |
32576 KB |
Output is correct |
15 |
Correct |
188 ms |
32452 KB |
Output is correct |
16 |
Correct |
248 ms |
32904 KB |
Output is correct |
17 |
Correct |
247 ms |
32820 KB |
Output is correct |
18 |
Correct |
223 ms |
33548 KB |
Output is correct |
19 |
Correct |
235 ms |
33732 KB |
Output is correct |
20 |
Correct |
241 ms |
32712 KB |
Output is correct |
21 |
Correct |
253 ms |
32804 KB |
Output is correct |
22 |
Correct |
258 ms |
32528 KB |
Output is correct |
23 |
Correct |
68 ms |
27984 KB |
Output is correct |
24 |
Correct |
198 ms |
37312 KB |
Output is correct |
25 |
Correct |
10 ms |
22360 KB |
Output is correct |
26 |
Correct |
4 ms |
21080 KB |
Output is correct |
27 |
Correct |
4 ms |
21080 KB |
Output is correct |
28 |
Correct |
14 ms |
24408 KB |
Output is correct |
29 |
Correct |
9 ms |
22872 KB |
Output is correct |
30 |
Correct |
5 ms |
21080 KB |
Output is correct |
31 |
Correct |
4 ms |
21336 KB |
Output is correct |
32 |
Correct |
5 ms |
21332 KB |
Output is correct |
33 |
Correct |
5 ms |
21080 KB |
Output is correct |
34 |
Correct |
9 ms |
22684 KB |
Output is correct |
35 |
Correct |
4 ms |
21080 KB |
Output is correct |
36 |
Correct |
4 ms |
21084 KB |
Output is correct |
37 |
Correct |
4 ms |
21080 KB |
Output is correct |
38 |
Correct |
4 ms |
21084 KB |
Output is correct |
39 |
Correct |
5 ms |
21080 KB |
Output is correct |
40 |
Correct |
205 ms |
36152 KB |
Output is correct |
41 |
Correct |
182 ms |
36552 KB |
Output is correct |
42 |
Correct |
177 ms |
36648 KB |
Output is correct |
43 |
Correct |
69 ms |
31300 KB |
Output is correct |
44 |
Correct |
74 ms |
31316 KB |
Output is correct |
45 |
Correct |
190 ms |
37828 KB |
Output is correct |
46 |
Correct |
190 ms |
37572 KB |
Output is correct |
47 |
Correct |
202 ms |
36248 KB |
Output is correct |
48 |
Correct |
80 ms |
30956 KB |
Output is correct |
49 |
Correct |
197 ms |
35900 KB |
Output is correct |
50 |
Correct |
202 ms |
37200 KB |
Output is correct |
51 |
Correct |
179 ms |
37816 KB |
Output is correct |