///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 3e5 + 10;
const ll INF = 1e18;
ll n, m, sp, tp, up, vp;
ll dis[5][MXN], dp[5][MXN], val[MXN];
bool mark[MXN];
vector<ll> adj[MXN], Ver;
vector<pair<ll, ll>> G[MXN];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
void DIJ(ll f, ll src){
for(int i = 1; i <= n; i ++){
dis[f][i] = INF, mark[i] = 0;
}
dis[f][src] = 0, pq.push({0, src});
while(!pq.empty()){
ll u, d; tie(d, u) = pq.top();
pq.pop();
if(mark[u]) continue;
mark[u] = 1;
for(auto Pr : G[u]){
ll v, w; tie(v, w) = Pr;
if(!mark[v] && d + w < dis[f][v]){
dis[f][v] = d + w;
pq.push({dis[f][v], v});
}
}
}
}
void Build(ll f, ll src, ll base){
for(int i = 1; i <= n; i ++) adj[i].clear();
for(int i = 1; i <= n; i ++) val[i] = dis[base][i];
for(int u = 1; u <= n; u ++){
for(auto Pr : G[u]){
ll v, w; tie(v, w) = Pr;
if(dis[f][v] + w == dis[f][u]){
adj[u].push_back(v);
}
}
}
}
bool cmpf;
bool CMP(ll u, ll v){
return dis[cmpf][u] < dis[cmpf][v];
}
void Calc(ll f, ll base){
for(int i = 1; i <= n; i ++) dp[f][i] = INF;
cmpf = base;
sort(Ver.begin(), Ver.end(), CMP);
for(auto u : Ver){
dp[f][u] = val[u];
for(auto v : adj[u]){
dp[f][u] = min(dp[f][u], dp[f][v]);
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> n >> m >> sp >> tp >> up >> vp;
for(int i = 1; i <= m; i ++){
ll u, v, w; cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
Ver.push_back(i);
}
DIJ(0, sp), DIJ(1, tp), DIJ(2, up), DIJ(3, vp);
Build(0, sp, 2);//up
Calc(0, 0);
Build(0, sp, 3);//vp
Calc(1, 0);
Build(1, tp, 2);//up
Calc(2, 1);
Build(1, tp, 3);//vp
Calc(3, 1);
ll ans = dis[2][vp];
for(int x = 1; x <= n; x ++){
if(dis[0][x] + dis[1][x] > dis[0][tp]) continue;
ll now = dis[2][x] + min(dp[1][x], dp[3][x]);
ans = min(ans, now);
}
cout << ans << '\n';
return 0;
}
/*!
HE'S AN INSTIGATOR,
ENEMY ELIMINATOR,
AND WHEN HE KNOCKS YOU BETTER
YOU BETTER LET HIM IN.
*/
//! N.N
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
499 ms |
40708 KB |
Output is correct |
2 |
Correct |
498 ms |
40668 KB |
Output is correct |
3 |
Correct |
497 ms |
40536 KB |
Output is correct |
4 |
Correct |
500 ms |
40792 KB |
Output is correct |
5 |
Correct |
495 ms |
40796 KB |
Output is correct |
6 |
Correct |
506 ms |
40796 KB |
Output is correct |
7 |
Correct |
504 ms |
40676 KB |
Output is correct |
8 |
Correct |
519 ms |
40540 KB |
Output is correct |
9 |
Correct |
510 ms |
40420 KB |
Output is correct |
10 |
Correct |
446 ms |
40544 KB |
Output is correct |
11 |
Correct |
244 ms |
30944 KB |
Output is correct |
12 |
Correct |
535 ms |
40412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
510 ms |
40540 KB |
Output is correct |
2 |
Correct |
507 ms |
40412 KB |
Output is correct |
3 |
Correct |
507 ms |
40548 KB |
Output is correct |
4 |
Correct |
517 ms |
40412 KB |
Output is correct |
5 |
Correct |
512 ms |
40540 KB |
Output is correct |
6 |
Correct |
496 ms |
40672 KB |
Output is correct |
7 |
Correct |
504 ms |
40540 KB |
Output is correct |
8 |
Correct |
511 ms |
40412 KB |
Output is correct |
9 |
Correct |
552 ms |
40412 KB |
Output is correct |
10 |
Correct |
513 ms |
40540 KB |
Output is correct |
11 |
Correct |
265 ms |
30816 KB |
Output is correct |
12 |
Correct |
519 ms |
40668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
17256 KB |
Output is correct |
2 |
Correct |
11 ms |
14572 KB |
Output is correct |
3 |
Correct |
10 ms |
14572 KB |
Output is correct |
4 |
Correct |
37 ms |
19556 KB |
Output is correct |
5 |
Correct |
31 ms |
17000 KB |
Output is correct |
6 |
Correct |
11 ms |
14700 KB |
Output is correct |
7 |
Correct |
13 ms |
14828 KB |
Output is correct |
8 |
Correct |
11 ms |
14956 KB |
Output is correct |
9 |
Correct |
11 ms |
14700 KB |
Output is correct |
10 |
Correct |
34 ms |
17128 KB |
Output is correct |
11 |
Correct |
9 ms |
14572 KB |
Output is correct |
12 |
Correct |
9 ms |
14572 KB |
Output is correct |
13 |
Correct |
9 ms |
14572 KB |
Output is correct |
14 |
Correct |
12 ms |
14572 KB |
Output is correct |
15 |
Correct |
11 ms |
14572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
499 ms |
40708 KB |
Output is correct |
2 |
Correct |
498 ms |
40668 KB |
Output is correct |
3 |
Correct |
497 ms |
40536 KB |
Output is correct |
4 |
Correct |
500 ms |
40792 KB |
Output is correct |
5 |
Correct |
495 ms |
40796 KB |
Output is correct |
6 |
Correct |
506 ms |
40796 KB |
Output is correct |
7 |
Correct |
504 ms |
40676 KB |
Output is correct |
8 |
Correct |
519 ms |
40540 KB |
Output is correct |
9 |
Correct |
510 ms |
40420 KB |
Output is correct |
10 |
Correct |
446 ms |
40544 KB |
Output is correct |
11 |
Correct |
244 ms |
30944 KB |
Output is correct |
12 |
Correct |
535 ms |
40412 KB |
Output is correct |
13 |
Correct |
510 ms |
40540 KB |
Output is correct |
14 |
Correct |
507 ms |
40412 KB |
Output is correct |
15 |
Correct |
507 ms |
40548 KB |
Output is correct |
16 |
Correct |
517 ms |
40412 KB |
Output is correct |
17 |
Correct |
512 ms |
40540 KB |
Output is correct |
18 |
Correct |
496 ms |
40672 KB |
Output is correct |
19 |
Correct |
504 ms |
40540 KB |
Output is correct |
20 |
Correct |
511 ms |
40412 KB |
Output is correct |
21 |
Correct |
552 ms |
40412 KB |
Output is correct |
22 |
Correct |
513 ms |
40540 KB |
Output is correct |
23 |
Correct |
265 ms |
30816 KB |
Output is correct |
24 |
Correct |
519 ms |
40668 KB |
Output is correct |
25 |
Correct |
24 ms |
17256 KB |
Output is correct |
26 |
Correct |
11 ms |
14572 KB |
Output is correct |
27 |
Correct |
10 ms |
14572 KB |
Output is correct |
28 |
Correct |
37 ms |
19556 KB |
Output is correct |
29 |
Correct |
31 ms |
17000 KB |
Output is correct |
30 |
Correct |
11 ms |
14700 KB |
Output is correct |
31 |
Correct |
13 ms |
14828 KB |
Output is correct |
32 |
Correct |
11 ms |
14956 KB |
Output is correct |
33 |
Correct |
11 ms |
14700 KB |
Output is correct |
34 |
Correct |
34 ms |
17128 KB |
Output is correct |
35 |
Correct |
9 ms |
14572 KB |
Output is correct |
36 |
Correct |
9 ms |
14572 KB |
Output is correct |
37 |
Correct |
9 ms |
14572 KB |
Output is correct |
38 |
Correct |
12 ms |
14572 KB |
Output is correct |
39 |
Correct |
11 ms |
14572 KB |
Output is correct |
40 |
Correct |
496 ms |
40288 KB |
Output is correct |
41 |
Correct |
528 ms |
40412 KB |
Output is correct |
42 |
Correct |
522 ms |
40400 KB |
Output is correct |
43 |
Correct |
301 ms |
30832 KB |
Output is correct |
44 |
Correct |
279 ms |
30816 KB |
Output is correct |
45 |
Correct |
535 ms |
41620 KB |
Output is correct |
46 |
Correct |
486 ms |
41564 KB |
Output is correct |
47 |
Correct |
535 ms |
41180 KB |
Output is correct |
48 |
Correct |
275 ms |
30944 KB |
Output is correct |
49 |
Correct |
472 ms |
40908 KB |
Output is correct |
50 |
Correct |
497 ms |
41308 KB |
Output is correct |
51 |
Correct |
480 ms |
41564 KB |
Output is correct |