#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl cout<<"\n"
#define f first
#define s second
#define ca(v) for(auto i:v) cout<<i<<" ";
const int MAXN = 1e5 + 5;
int n, m, S, T, U, V;
vector<pair<int, int>> adj[MAXN];
ll dst[MAXN][4];
ll vis[MAXN][3];
ll ans;
ll bst;
void dijkstra(int x, int p){
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
for(int i=0; i<n; i++) dst[i][p] = 2e18;
dst[x][p] = 0;
q.push({0, x});
while(q.size()){
auto c = q.top(); q.pop();
int x = c.s; ll w = c.f;
if(dst[x][p] < w) continue;
for(auto a : adj[x]){
if(w + a.s < dst[a.f][p]){
dst[a.f][p] = w + a.s;
q.push({dst[a.f][p], a.f});
}
}
}
}
struct nd{
int x; ll w; int id;
friend bool operator<(nd a, nd b){ return a.x > b.x; }
};
void solve(){
for(int i=0; i<n; i++) vis[i][0] = vis[i][1] = vis[i][2] = 2e18;
vis[S][0] = 0;
priority_queue<nd> q;
q.push({S, 0, 0});
while(q.size()){
auto c = q.top(); q.pop();
if(vis[c.x][c.id] < c.w) continue;
for(auto a:adj[c.x]){
if(dst[c.x][0] + a.s + dst[a.f][1] == bst){
if(c.w < vis[a.f][c.id]){
vis[a.f][c.id] = c.w;
q.push({a.f, c.w, c.id});
}
}
}
if(c.id == 1){
// cout<<c.x<<" "<<c.w<<" "<<c.id<<"\n";
ans = min(ans, c.w + dst[c.x][3]);
}
else if(c.id == 2){
ans = min(ans, c.w + dst[c.x][2]);
}
else{
if(dst[c.x][2]<vis[c.x][1]) q.push({c.x, dst[c.x][2], 1});
if(dst[c.x][3]<vis[c.x][2]) q.push({c.x, dst[c.x][3], 2});
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
cin>>n>>m;
cin>>S>>T>>U>>V;
S--; T--; U--; V--;
for(int i=0; i<m; i++){
int u, v, x; cin>>u>>v>>x;
u--; v--;
adj[u].push_back({v, x});
adj[v].push_back({u, x});
}
dijkstra(S, 0);
dijkstra(T, 1);
dijkstra(U, 2);
dijkstra(V, 3);
// for(int i=0; i<n; i++) cout<<dst[i][1]<<" ";
bst = dst[T][0];
ans = dst[V][2];
solve();
cout<<ans;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:73:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
320 ms |
19064 KB |
Output is correct |
2 |
Correct |
378 ms |
17944 KB |
Output is correct |
3 |
Correct |
408 ms |
19760 KB |
Output is correct |
4 |
Correct |
285 ms |
18928 KB |
Output is correct |
5 |
Correct |
354 ms |
18164 KB |
Output is correct |
6 |
Correct |
287 ms |
19072 KB |
Output is correct |
7 |
Correct |
393 ms |
17884 KB |
Output is correct |
8 |
Correct |
369 ms |
17944 KB |
Output is correct |
9 |
Correct |
275 ms |
18872 KB |
Output is correct |
10 |
Correct |
221 ms |
18856 KB |
Output is correct |
11 |
Correct |
142 ms |
13168 KB |
Output is correct |
12 |
Correct |
266 ms |
18628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
326 ms |
18128 KB |
Output is correct |
2 |
Correct |
334 ms |
17888 KB |
Output is correct |
3 |
Correct |
361 ms |
17984 KB |
Output is correct |
4 |
Correct |
317 ms |
17968 KB |
Output is correct |
5 |
Correct |
372 ms |
18008 KB |
Output is correct |
6 |
Correct |
333 ms |
18212 KB |
Output is correct |
7 |
Correct |
454 ms |
17984 KB |
Output is correct |
8 |
Correct |
348 ms |
17916 KB |
Output is correct |
9 |
Correct |
354 ms |
18100 KB |
Output is correct |
10 |
Correct |
312 ms |
17892 KB |
Output is correct |
11 |
Correct |
211 ms |
13496 KB |
Output is correct |
12 |
Correct |
334 ms |
18124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
3800 KB |
Output is correct |
2 |
Correct |
2 ms |
2672 KB |
Output is correct |
3 |
Correct |
2 ms |
2676 KB |
Output is correct |
4 |
Correct |
18 ms |
4744 KB |
Output is correct |
5 |
Correct |
9 ms |
3644 KB |
Output is correct |
6 |
Correct |
2 ms |
2764 KB |
Output is correct |
7 |
Correct |
4 ms |
2764 KB |
Output is correct |
8 |
Correct |
3 ms |
2796 KB |
Output is correct |
9 |
Correct |
2 ms |
2668 KB |
Output is correct |
10 |
Correct |
8 ms |
3696 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2676 KB |
Output is correct |
15 |
Correct |
2 ms |
2680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
320 ms |
19064 KB |
Output is correct |
2 |
Correct |
378 ms |
17944 KB |
Output is correct |
3 |
Correct |
408 ms |
19760 KB |
Output is correct |
4 |
Correct |
285 ms |
18928 KB |
Output is correct |
5 |
Correct |
354 ms |
18164 KB |
Output is correct |
6 |
Correct |
287 ms |
19072 KB |
Output is correct |
7 |
Correct |
393 ms |
17884 KB |
Output is correct |
8 |
Correct |
369 ms |
17944 KB |
Output is correct |
9 |
Correct |
275 ms |
18872 KB |
Output is correct |
10 |
Correct |
221 ms |
18856 KB |
Output is correct |
11 |
Correct |
142 ms |
13168 KB |
Output is correct |
12 |
Correct |
266 ms |
18628 KB |
Output is correct |
13 |
Correct |
326 ms |
18128 KB |
Output is correct |
14 |
Correct |
334 ms |
17888 KB |
Output is correct |
15 |
Correct |
361 ms |
17984 KB |
Output is correct |
16 |
Correct |
317 ms |
17968 KB |
Output is correct |
17 |
Correct |
372 ms |
18008 KB |
Output is correct |
18 |
Correct |
333 ms |
18212 KB |
Output is correct |
19 |
Correct |
454 ms |
17984 KB |
Output is correct |
20 |
Correct |
348 ms |
17916 KB |
Output is correct |
21 |
Correct |
354 ms |
18100 KB |
Output is correct |
22 |
Correct |
312 ms |
17892 KB |
Output is correct |
23 |
Correct |
211 ms |
13496 KB |
Output is correct |
24 |
Correct |
334 ms |
18124 KB |
Output is correct |
25 |
Correct |
10 ms |
3800 KB |
Output is correct |
26 |
Correct |
2 ms |
2672 KB |
Output is correct |
27 |
Correct |
2 ms |
2676 KB |
Output is correct |
28 |
Correct |
18 ms |
4744 KB |
Output is correct |
29 |
Correct |
9 ms |
3644 KB |
Output is correct |
30 |
Correct |
2 ms |
2764 KB |
Output is correct |
31 |
Correct |
4 ms |
2764 KB |
Output is correct |
32 |
Correct |
3 ms |
2796 KB |
Output is correct |
33 |
Correct |
2 ms |
2668 KB |
Output is correct |
34 |
Correct |
8 ms |
3696 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
2 ms |
2636 KB |
Output is correct |
37 |
Correct |
2 ms |
2636 KB |
Output is correct |
38 |
Correct |
2 ms |
2676 KB |
Output is correct |
39 |
Correct |
2 ms |
2680 KB |
Output is correct |
40 |
Correct |
299 ms |
19448 KB |
Output is correct |
41 |
Correct |
320 ms |
18712 KB |
Output is correct |
42 |
Correct |
282 ms |
18768 KB |
Output is correct |
43 |
Correct |
210 ms |
13372 KB |
Output is correct |
44 |
Correct |
243 ms |
13316 KB |
Output is correct |
45 |
Correct |
680 ms |
20368 KB |
Output is correct |
46 |
Correct |
515 ms |
20040 KB |
Output is correct |
47 |
Correct |
324 ms |
18896 KB |
Output is correct |
48 |
Correct |
288 ms |
12804 KB |
Output is correct |
49 |
Correct |
259 ms |
19188 KB |
Output is correct |
50 |
Correct |
719 ms |
20740 KB |
Output is correct |
51 |
Correct |
406 ms |
19200 KB |
Output is correct |