#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
const int INF = 1e18, MOD = 1e9 + 7, N = 1e5 + 1;
void setIO(string name = ""){
ios::sync_with_stdio(false);
cin.tie(0);
if(name.size()){
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
using pii = pair<int, int>;
vector<pii> adj[N];
int disu[N], disv[N], diss[N], vis[N], ans, dp[2][N];
void getdis(int start, int dis[]){
fill(vis, vis + N, false);
priority_queue<pii> pq;
pq.push({0, start});
dis[start] = 0;
while(!pq.empty()){
int c, cur;
tie(c, cur) = pq.top();
pq.pop();
if(!vis[cur]){
dis[cur] = -c;
vis[cur] = 1;
for(auto nxt : adj[cur])pq.push({c - nxt.first, nxt.second});
}
}
}
void dijkstra(int start, int end){
fill(vis, vis + N, false);
fill(dp[0], dp[0] + N, INF);
fill(dp[1], dp[1] + N, INF);
priority_queue<pair<int, pii>> pq;
pq.push({0, {start, 0}});
while(!pq.empty()){
int c, cur, par;
pii tmp;
tie(c, tmp) = pq.top();
tie(cur, par) = tmp;
pq.pop();
if(!vis[cur]){
vis[cur] = 1;
dp[0][cur] = min(disu[cur], dp[0][par]);
dp[1][cur] = min(disv[cur], dp[1][par]);
diss[cur] = -c;
for(auto nxt : adj[cur])pq.push({c - nxt.first, {nxt.second, cur}});
}else if(diss[cur] == -c){
if(min(disu[cur], dp[0][par]) + min(disv[cur], dp[1][par]) < dp[0][cur] + dp[1][cur]){
dp[0][cur] = min(disu[cur], dp[0][par]);
dp[1][cur] = min(disv[cur], dp[1][par]);
}
}
}
ans = min(ans, dp[0][end] + dp[1][end]);
}
signed main(){
setIO();
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({c, b});
adj[b].push_back({c, a});
}
getdis(u, disu);
getdis(v, disv);
ans = disu[v];
dijkstra(s, t);
dijkstra(t, s);
cout << ans;
}
Compilation message
commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
665 ms |
31672 KB |
Output is correct |
2 |
Correct |
577 ms |
30824 KB |
Output is correct |
3 |
Correct |
586 ms |
30648 KB |
Output is correct |
4 |
Correct |
708 ms |
30832 KB |
Output is correct |
5 |
Correct |
570 ms |
27152 KB |
Output is correct |
6 |
Correct |
672 ms |
31804 KB |
Output is correct |
7 |
Correct |
561 ms |
30744 KB |
Output is correct |
8 |
Correct |
564 ms |
30916 KB |
Output is correct |
9 |
Correct |
650 ms |
32052 KB |
Output is correct |
10 |
Correct |
615 ms |
32220 KB |
Output is correct |
11 |
Correct |
185 ms |
14532 KB |
Output is correct |
12 |
Correct |
623 ms |
32272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
603 ms |
31284 KB |
Output is correct |
2 |
Correct |
567 ms |
27232 KB |
Output is correct |
3 |
Correct |
555 ms |
30576 KB |
Output is correct |
4 |
Correct |
595 ms |
27472 KB |
Output is correct |
5 |
Correct |
534 ms |
27052 KB |
Output is correct |
6 |
Correct |
562 ms |
30664 KB |
Output is correct |
7 |
Correct |
556 ms |
26972 KB |
Output is correct |
8 |
Correct |
588 ms |
27276 KB |
Output is correct |
9 |
Correct |
570 ms |
27012 KB |
Output is correct |
10 |
Correct |
572 ms |
30432 KB |
Output is correct |
11 |
Correct |
173 ms |
14656 KB |
Output is correct |
12 |
Correct |
603 ms |
30820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
8136 KB |
Output is correct |
2 |
Correct |
5 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
88 ms |
11284 KB |
Output is correct |
5 |
Correct |
45 ms |
9124 KB |
Output is correct |
6 |
Correct |
6 ms |
5196 KB |
Output is correct |
7 |
Correct |
7 ms |
5324 KB |
Output is correct |
8 |
Correct |
9 ms |
5432 KB |
Output is correct |
9 |
Correct |
5 ms |
5196 KB |
Output is correct |
10 |
Correct |
44 ms |
9008 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
5068 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
5 ms |
5196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
665 ms |
31672 KB |
Output is correct |
2 |
Correct |
577 ms |
30824 KB |
Output is correct |
3 |
Correct |
586 ms |
30648 KB |
Output is correct |
4 |
Correct |
708 ms |
30832 KB |
Output is correct |
5 |
Correct |
570 ms |
27152 KB |
Output is correct |
6 |
Correct |
672 ms |
31804 KB |
Output is correct |
7 |
Correct |
561 ms |
30744 KB |
Output is correct |
8 |
Correct |
564 ms |
30916 KB |
Output is correct |
9 |
Correct |
650 ms |
32052 KB |
Output is correct |
10 |
Correct |
615 ms |
32220 KB |
Output is correct |
11 |
Correct |
185 ms |
14532 KB |
Output is correct |
12 |
Correct |
623 ms |
32272 KB |
Output is correct |
13 |
Correct |
603 ms |
31284 KB |
Output is correct |
14 |
Correct |
567 ms |
27232 KB |
Output is correct |
15 |
Correct |
555 ms |
30576 KB |
Output is correct |
16 |
Correct |
595 ms |
27472 KB |
Output is correct |
17 |
Correct |
534 ms |
27052 KB |
Output is correct |
18 |
Correct |
562 ms |
30664 KB |
Output is correct |
19 |
Correct |
556 ms |
26972 KB |
Output is correct |
20 |
Correct |
588 ms |
27276 KB |
Output is correct |
21 |
Correct |
570 ms |
27012 KB |
Output is correct |
22 |
Correct |
572 ms |
30432 KB |
Output is correct |
23 |
Correct |
173 ms |
14656 KB |
Output is correct |
24 |
Correct |
603 ms |
30820 KB |
Output is correct |
25 |
Correct |
46 ms |
8136 KB |
Output is correct |
26 |
Correct |
5 ms |
5068 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
88 ms |
11284 KB |
Output is correct |
29 |
Correct |
45 ms |
9124 KB |
Output is correct |
30 |
Correct |
6 ms |
5196 KB |
Output is correct |
31 |
Correct |
7 ms |
5324 KB |
Output is correct |
32 |
Correct |
9 ms |
5432 KB |
Output is correct |
33 |
Correct |
5 ms |
5196 KB |
Output is correct |
34 |
Correct |
44 ms |
9008 KB |
Output is correct |
35 |
Correct |
4 ms |
4940 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
4 ms |
5068 KB |
Output is correct |
39 |
Correct |
5 ms |
5196 KB |
Output is correct |
40 |
Correct |
631 ms |
31752 KB |
Output is correct |
41 |
Correct |
685 ms |
32024 KB |
Output is correct |
42 |
Correct |
625 ms |
31900 KB |
Output is correct |
43 |
Correct |
161 ms |
14688 KB |
Output is correct |
44 |
Correct |
179 ms |
14768 KB |
Output is correct |
45 |
Correct |
549 ms |
25792 KB |
Output is correct |
46 |
Correct |
576 ms |
25620 KB |
Output is correct |
47 |
Correct |
622 ms |
27420 KB |
Output is correct |
48 |
Correct |
196 ms |
14020 KB |
Output is correct |
49 |
Correct |
623 ms |
30052 KB |
Output is correct |
50 |
Correct |
567 ms |
25940 KB |
Output is correct |
51 |
Correct |
590 ms |
25784 KB |
Output is correct |