/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e6+100, M = 1e5+10, K = 20;
const ll LMX = 1e16;
int n, m, s, t, x, y;
ll dx[N], dy[N], d[N], minx[N], miny[N];
vector<array<ll, 3>> g[N];
vector<bool> vis;
void solve(){
cin >> n >> m >> s >> t >> x >> y;
for(int i = 0; i < m; ++i){
int u, v, w; cin >> u >> v >> w;
g[u].pb({v, w, i});
g[v].pb({u, w, i});
}
vis.resize(n + 1);
//first dijkstra
priority_queue<pair<ll, int>> q;
q.push({0, x});
for(int i = 1; i <= n; ++i) dx[i] = i == x ? 0 : LMX;
for(int i = 1; i <= n; ++i) dy[i] = i == y ? 0 : LMX;
for(int i = 1; i <= n; ++i) d[i] = i == s ? 0 : LMX;
for(int i = 1; i <= n; ++i) minx[i] = LMX;
for(int i = 1; i <= n; ++i) miny[i] = LMX;
dx[0] = 0;
while(!q.empty()){
int v = q.top().second; q.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto U: g[v]){
int u = U[0], w = U[1];
if(!vis[u] && dx[u] > dx[v] + w){
dx[u] = dx[v] + w;
q.push({-dx[u], u});
}
}
}
fill(all(vis), 0);
q.push({0, y});
dy[0] = 0;
while(!q.empty()){
int v = q.top().second; q.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto U: g[v]){
int u = U[0], w = U[1];
if(!vis[u] && dy[u] > dy[v] + w){
dy[u] = dy[v] + w;
q.push({-dy[u], u});
}
}
}
priority_queue<array<ll, 2>> Q; // dist, node, min_x_dist
Q.push({0, s});
d[s] = 0;
fill(all(vis), 0);
while(!Q.empty()){
int v = Q.top()[1];
Q.pop();
if(vis[v]) continue;
minx[v] = dx[v];
miny[v] = dy[v];
vis[v] = 1;
for(auto U: g[v]){
int u = U[0], w = U[1];
if(vis[u] && d[v] == d[u] + w){
minx[v] = min(minx[u], minx[v]);
miny[v] = min(miny[u], miny[v]);
}
if(!vis[u] && d[u] > d[v] + w){
d[u] = d[v] + w;
Q.push({-d[u], u});
}
}
}
ll ans = LMX;
queue<int> qu; qu.push(t);
fill(all(vis), 0);
vis[t] = 1;
while(!qu.empty()){
int v = qu.front();
qu.pop();
ans = min(ans, minx[v] + dy[v]);
ans = min(ans, miny[v] + dx[v]);
for(auto U: g[v]){
int u = U[0], w = U[1];
if(d[u] == d[v] - w){
if(!vis[u]){
vis[u] = 1;
qu.push(u);
}
}
}
}
for(int i = 1; i <= n; ++i) ans = min(ans, dx[i] + dy[i]);
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int T = 1, aa;
// cin >> T;aa=T;
while(T--){
// cout << "Case #" << aa-T << ": ";
solve();
cout << '\n';
}
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:123:14: warning: unused variable 'aa' [-Wunused-variable]
123 | int T = 1, aa;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
242 ms |
46492 KB |
Output is correct |
2 |
Correct |
254 ms |
44868 KB |
Output is correct |
3 |
Correct |
256 ms |
44528 KB |
Output is correct |
4 |
Correct |
251 ms |
45316 KB |
Output is correct |
5 |
Correct |
265 ms |
44732 KB |
Output is correct |
6 |
Correct |
251 ms |
46484 KB |
Output is correct |
7 |
Correct |
254 ms |
44736 KB |
Output is correct |
8 |
Correct |
264 ms |
44948 KB |
Output is correct |
9 |
Correct |
247 ms |
44708 KB |
Output is correct |
10 |
Correct |
224 ms |
44408 KB |
Output is correct |
11 |
Correct |
110 ms |
34252 KB |
Output is correct |
12 |
Correct |
260 ms |
44756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
265 ms |
44968 KB |
Output is correct |
2 |
Correct |
275 ms |
44904 KB |
Output is correct |
3 |
Correct |
262 ms |
44820 KB |
Output is correct |
4 |
Correct |
259 ms |
44848 KB |
Output is correct |
5 |
Correct |
265 ms |
44808 KB |
Output is correct |
6 |
Correct |
253 ms |
44688 KB |
Output is correct |
7 |
Correct |
278 ms |
44784 KB |
Output is correct |
8 |
Correct |
266 ms |
44808 KB |
Output is correct |
9 |
Correct |
262 ms |
44884 KB |
Output is correct |
10 |
Correct |
273 ms |
44968 KB |
Output is correct |
11 |
Correct |
117 ms |
34340 KB |
Output is correct |
12 |
Correct |
258 ms |
44664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
26016 KB |
Output is correct |
2 |
Correct |
12 ms |
23840 KB |
Output is correct |
3 |
Correct |
12 ms |
23848 KB |
Output is correct |
4 |
Correct |
25 ms |
27680 KB |
Output is correct |
5 |
Correct |
18 ms |
25924 KB |
Output is correct |
6 |
Correct |
12 ms |
23920 KB |
Output is correct |
7 |
Correct |
14 ms |
24020 KB |
Output is correct |
8 |
Correct |
14 ms |
24068 KB |
Output is correct |
9 |
Correct |
15 ms |
23972 KB |
Output is correct |
10 |
Correct |
19 ms |
25812 KB |
Output is correct |
11 |
Correct |
12 ms |
23764 KB |
Output is correct |
12 |
Correct |
12 ms |
23860 KB |
Output is correct |
13 |
Correct |
13 ms |
23892 KB |
Output is correct |
14 |
Correct |
13 ms |
23892 KB |
Output is correct |
15 |
Correct |
14 ms |
23892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
242 ms |
46492 KB |
Output is correct |
2 |
Correct |
254 ms |
44868 KB |
Output is correct |
3 |
Correct |
256 ms |
44528 KB |
Output is correct |
4 |
Correct |
251 ms |
45316 KB |
Output is correct |
5 |
Correct |
265 ms |
44732 KB |
Output is correct |
6 |
Correct |
251 ms |
46484 KB |
Output is correct |
7 |
Correct |
254 ms |
44736 KB |
Output is correct |
8 |
Correct |
264 ms |
44948 KB |
Output is correct |
9 |
Correct |
247 ms |
44708 KB |
Output is correct |
10 |
Correct |
224 ms |
44408 KB |
Output is correct |
11 |
Correct |
110 ms |
34252 KB |
Output is correct |
12 |
Correct |
260 ms |
44756 KB |
Output is correct |
13 |
Correct |
265 ms |
44968 KB |
Output is correct |
14 |
Correct |
275 ms |
44904 KB |
Output is correct |
15 |
Correct |
262 ms |
44820 KB |
Output is correct |
16 |
Correct |
259 ms |
44848 KB |
Output is correct |
17 |
Correct |
265 ms |
44808 KB |
Output is correct |
18 |
Correct |
253 ms |
44688 KB |
Output is correct |
19 |
Correct |
278 ms |
44784 KB |
Output is correct |
20 |
Correct |
266 ms |
44808 KB |
Output is correct |
21 |
Correct |
262 ms |
44884 KB |
Output is correct |
22 |
Correct |
273 ms |
44968 KB |
Output is correct |
23 |
Correct |
117 ms |
34340 KB |
Output is correct |
24 |
Correct |
258 ms |
44664 KB |
Output is correct |
25 |
Correct |
18 ms |
26016 KB |
Output is correct |
26 |
Correct |
12 ms |
23840 KB |
Output is correct |
27 |
Correct |
12 ms |
23848 KB |
Output is correct |
28 |
Correct |
25 ms |
27680 KB |
Output is correct |
29 |
Correct |
18 ms |
25924 KB |
Output is correct |
30 |
Correct |
12 ms |
23920 KB |
Output is correct |
31 |
Correct |
14 ms |
24020 KB |
Output is correct |
32 |
Correct |
14 ms |
24068 KB |
Output is correct |
33 |
Correct |
15 ms |
23972 KB |
Output is correct |
34 |
Correct |
19 ms |
25812 KB |
Output is correct |
35 |
Correct |
12 ms |
23764 KB |
Output is correct |
36 |
Correct |
12 ms |
23860 KB |
Output is correct |
37 |
Correct |
13 ms |
23892 KB |
Output is correct |
38 |
Correct |
13 ms |
23892 KB |
Output is correct |
39 |
Correct |
14 ms |
23892 KB |
Output is correct |
40 |
Correct |
240 ms |
50212 KB |
Output is correct |
41 |
Correct |
277 ms |
48940 KB |
Output is correct |
42 |
Correct |
248 ms |
49024 KB |
Output is correct |
43 |
Correct |
123 ms |
36404 KB |
Output is correct |
44 |
Correct |
123 ms |
36456 KB |
Output is correct |
45 |
Correct |
247 ms |
47928 KB |
Output is correct |
46 |
Correct |
241 ms |
47588 KB |
Output is correct |
47 |
Correct |
257 ms |
48900 KB |
Output is correct |
48 |
Correct |
131 ms |
35876 KB |
Output is correct |
49 |
Correct |
222 ms |
49932 KB |
Output is correct |
50 |
Correct |
253 ms |
48204 KB |
Output is correct |
51 |
Correct |
251 ms |
47872 KB |
Output is correct |