#include<bits/stdc++.h>
#define ll long long
#define pii pair<long long, int>
const int N = 1e9 + 7;
using namespace std;
//khai bao
int n, m, s, t, x, y;
vector<pii> ke[100009];
// dijkstra
priority_queue<pii, vector<pii>, greater<pii> > p;
ll f[100009][2];
pair<ll, ll> g[100009];
ll dijkstra(int s, int t, int id){
while(p.size()) p.pop();
for(int i = 0; i <= n; i ++)
f[i][id] = 1e18;
f[s][id] = 0;
p.push({0, s});
while(p.size()){
pii o = p.top();
p.pop();
if(f[o.second][id] != o.first) continue;
if(o.second == t) return o.first;
for(pii i : ke[o.second])
if(f[i.second][id] > o.first + i.first){
f[i.second][id] = o.first + i.first;
p.push({f[i.second][id], i.second});
}
}
return 0;
}
/// tinh toan
struct kt{
ll w, w1, w2, u;
};
struct sx{
bool operator()(kt a, kt b){
if(a.w == b.w) return (a.w2 + a.w1) > (b.w2 + b.w1);
return a.w > b.w;
}
};
priority_queue<kt, vector<kt>, sx> q;
ll tinh(){
for(int i = 1; i <= n; i ++)
g[i] = {1e18, 1e18};
q.push({0, f[s][0], f[s][1], s});
g[s] = {0, f[s][0] + f[s][1]};
while(q.size()){
kt o = q.top();
// cout << o.u << " " << o.w << " " << o.w1 << " " << o.w2 << '\n';
q.pop();
if(o.u == t) return o.w1 + o.w2;
pair<ll, ll> y;
y = {o.w, o.w1 + o.w2};
if(g[o.u] != y) continue;
for(pii i : ke[o.u]){
y = {o.w + i.first, min(o.w1, f[i.second][0]) + min(o.w2, f[i.second][1])};
if(g[i.second] > y){
g[i.second] = {o.w + i.first, min(o.w1, f[i.second][0]) + min(o.w2, f[i.second][1])};
q.push({g[i.second].first, min(o.w1, f[i.second][0]), min(o.w2, f[i.second][1]), i.second});
}
}
}
return 2;
}
/// main mannnnnnnn
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen("bus.inp", "r", stdin);
//freopen("bus.out", "w", stdout);
cin >> n >> m >> s >> t >> x >> y;
int u, v, w;
while(m --){
cin >> u >> v >> w;
ke[u].push_back({w, v});
ke[v].push_back({w, u});
}
ll res = dijkstra(x, y, 0);
ll l = dijkstra(x, 0, 0);
l = dijkstra(y, 0, 1);
res = min(res, tinh());
cout << res;
}
//8 8
//1 6
//3 8
//1 2 3
//2 4 2
//2 3 3
//4 5 3
//3 5 2
//5 6 3
//2 7 4
//8 2 3
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:80:8: warning: variable 'l' set but not used [-Wunused-but-set-variable]
80 | ll l = dijkstra(x, 0, 0);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
22848 KB |
Output is correct |
2 |
Correct |
160 ms |
19404 KB |
Output is correct |
3 |
Correct |
172 ms |
19020 KB |
Output is correct |
4 |
Correct |
163 ms |
22348 KB |
Output is correct |
5 |
Correct |
165 ms |
22428 KB |
Output is correct |
6 |
Correct |
172 ms |
26180 KB |
Output is correct |
7 |
Correct |
153 ms |
22600 KB |
Output is correct |
8 |
Correct |
156 ms |
22944 KB |
Output is correct |
9 |
Correct |
142 ms |
23072 KB |
Output is correct |
10 |
Correct |
143 ms |
20292 KB |
Output is correct |
11 |
Correct |
53 ms |
11112 KB |
Output is correct |
12 |
Correct |
201 ms |
19524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
19320 KB |
Output is correct |
2 |
Correct |
169 ms |
19276 KB |
Output is correct |
3 |
Correct |
173 ms |
19300 KB |
Output is correct |
4 |
Correct |
188 ms |
19240 KB |
Output is correct |
5 |
Correct |
176 ms |
19352 KB |
Output is correct |
6 |
Correct |
190 ms |
19292 KB |
Output is correct |
7 |
Correct |
162 ms |
19272 KB |
Output is correct |
8 |
Correct |
175 ms |
19340 KB |
Output is correct |
9 |
Correct |
156 ms |
19344 KB |
Output is correct |
10 |
Correct |
175 ms |
19280 KB |
Output is correct |
11 |
Correct |
53 ms |
11092 KB |
Output is correct |
12 |
Correct |
178 ms |
19016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7256 KB |
Output is correct |
2 |
Correct |
2 ms |
5724 KB |
Output is correct |
3 |
Correct |
2 ms |
5724 KB |
Output is correct |
4 |
Correct |
11 ms |
9104 KB |
Output is correct |
5 |
Correct |
6 ms |
7516 KB |
Output is correct |
6 |
Correct |
2 ms |
5724 KB |
Output is correct |
7 |
Correct |
2 ms |
5980 KB |
Output is correct |
8 |
Correct |
2 ms |
5980 KB |
Output is correct |
9 |
Correct |
2 ms |
5872 KB |
Output is correct |
10 |
Correct |
6 ms |
7516 KB |
Output is correct |
11 |
Correct |
2 ms |
5724 KB |
Output is correct |
12 |
Correct |
1 ms |
5724 KB |
Output is correct |
13 |
Correct |
1 ms |
5724 KB |
Output is correct |
14 |
Correct |
2 ms |
5724 KB |
Output is correct |
15 |
Correct |
2 ms |
5724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
22848 KB |
Output is correct |
2 |
Correct |
160 ms |
19404 KB |
Output is correct |
3 |
Correct |
172 ms |
19020 KB |
Output is correct |
4 |
Correct |
163 ms |
22348 KB |
Output is correct |
5 |
Correct |
165 ms |
22428 KB |
Output is correct |
6 |
Correct |
172 ms |
26180 KB |
Output is correct |
7 |
Correct |
153 ms |
22600 KB |
Output is correct |
8 |
Correct |
156 ms |
22944 KB |
Output is correct |
9 |
Correct |
142 ms |
23072 KB |
Output is correct |
10 |
Correct |
143 ms |
20292 KB |
Output is correct |
11 |
Correct |
53 ms |
11112 KB |
Output is correct |
12 |
Correct |
201 ms |
19524 KB |
Output is correct |
13 |
Correct |
155 ms |
19320 KB |
Output is correct |
14 |
Correct |
169 ms |
19276 KB |
Output is correct |
15 |
Correct |
173 ms |
19300 KB |
Output is correct |
16 |
Correct |
188 ms |
19240 KB |
Output is correct |
17 |
Correct |
176 ms |
19352 KB |
Output is correct |
18 |
Correct |
190 ms |
19292 KB |
Output is correct |
19 |
Correct |
162 ms |
19272 KB |
Output is correct |
20 |
Correct |
175 ms |
19340 KB |
Output is correct |
21 |
Correct |
156 ms |
19344 KB |
Output is correct |
22 |
Correct |
175 ms |
19280 KB |
Output is correct |
23 |
Correct |
53 ms |
11092 KB |
Output is correct |
24 |
Correct |
178 ms |
19016 KB |
Output is correct |
25 |
Correct |
7 ms |
7256 KB |
Output is correct |
26 |
Correct |
2 ms |
5724 KB |
Output is correct |
27 |
Correct |
2 ms |
5724 KB |
Output is correct |
28 |
Correct |
11 ms |
9104 KB |
Output is correct |
29 |
Correct |
6 ms |
7516 KB |
Output is correct |
30 |
Correct |
2 ms |
5724 KB |
Output is correct |
31 |
Correct |
2 ms |
5980 KB |
Output is correct |
32 |
Correct |
2 ms |
5980 KB |
Output is correct |
33 |
Correct |
2 ms |
5872 KB |
Output is correct |
34 |
Correct |
6 ms |
7516 KB |
Output is correct |
35 |
Correct |
2 ms |
5724 KB |
Output is correct |
36 |
Correct |
1 ms |
5724 KB |
Output is correct |
37 |
Correct |
1 ms |
5724 KB |
Output is correct |
38 |
Correct |
2 ms |
5724 KB |
Output is correct |
39 |
Correct |
2 ms |
5724 KB |
Output is correct |
40 |
Correct |
183 ms |
23032 KB |
Output is correct |
41 |
Correct |
125 ms |
17884 KB |
Output is correct |
42 |
Correct |
169 ms |
19288 KB |
Output is correct |
43 |
Correct |
51 ms |
11092 KB |
Output is correct |
44 |
Correct |
49 ms |
11068 KB |
Output is correct |
45 |
Correct |
172 ms |
19240 KB |
Output is correct |
46 |
Correct |
156 ms |
18764 KB |
Output is correct |
47 |
Correct |
186 ms |
21456 KB |
Output is correct |
48 |
Correct |
85 ms |
11088 KB |
Output is correct |
49 |
Correct |
174 ms |
22156 KB |
Output is correct |
50 |
Correct |
142 ms |
19156 KB |
Output is correct |
51 |
Correct |
126 ms |
18956 KB |
Output is correct |