#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;
int n, m;
int S, T, U, V;
vector<pii> G[MX];
void nhap(){
cin >> n >> m;
cin >> S >> T >> U >> V;
for(int i=1; i<=m; i++){
int u, v, c;
cin >> u >> v >> c;
G[u].push_back({v, c});
G[v].push_back({u, c});
}
}
void dijkstra(int u, int *d){
for(int i=1; i<=n; i++) d[i] = 1e18;
priority_queue<pii> Q;
Q.push({0, u});
d[u] = 0;
while(Q.size()){
int du, u;
tie(du, u) = Q.top();
du = -du;
Q.pop();
if(du != d[u]) continue;
for(pii &tmp: G[u]){
int v, c; tie(v, c) = tmp;
c += du;
if(c < d[v]){
d[v] = c;
Q.push({-c, v});
}
}
}
}
int dS[MX];
int dT[MX];
int dU[MX];
int dV[MX];
int f1[MX];
int f2[MX];
void solve(){
dijkstra(S, dS);
dijkstra(T, dT);
dijkstra(U, dU);
dijkstra(V, dV);
int ans = dU[V];
{
bitset<MX> vist = 0;
vector<int> vt(n);
for(int i=1; i<=n; i++) vt[i-1] = i;
function<bool(const int &, const int &)> comp = [&](const int &a, const int &b){
return dS[a] < dS[b];
};
sort(vt.begin(), vt.end(), comp);
for(int u: vt) if(dS[u] + dT[u] == dS[T]){
f1[u] = dU[u];
f2[u] = dV[u];
for(pii tmp: G[u]){
int v, c; tie(v, c) = tmp;
if(dS[v] + c == dS[u]){
f1[u] = min(f1[u], f1[v]);
f2[u] = min(f2[u], f2[v]);
}
}
ans = min({ans, f1[u] + dV[u], f2[u] + dU[u]});
}
}
cout << ans;
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:76:20: warning: variable 'vist' set but not used [-Wunused-but-set-variable]
76 | bitset<MX> vist = 0;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
25676 KB |
Output is correct |
2 |
Correct |
206 ms |
25660 KB |
Output is correct |
3 |
Correct |
200 ms |
26544 KB |
Output is correct |
4 |
Correct |
240 ms |
25648 KB |
Output is correct |
5 |
Correct |
200 ms |
25668 KB |
Output is correct |
6 |
Correct |
202 ms |
25892 KB |
Output is correct |
7 |
Correct |
223 ms |
25640 KB |
Output is correct |
8 |
Correct |
214 ms |
25600 KB |
Output is correct |
9 |
Correct |
196 ms |
25416 KB |
Output is correct |
10 |
Correct |
155 ms |
25372 KB |
Output is correct |
11 |
Correct |
72 ms |
20336 KB |
Output is correct |
12 |
Correct |
206 ms |
25296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
25548 KB |
Output is correct |
2 |
Correct |
219 ms |
25544 KB |
Output is correct |
3 |
Correct |
226 ms |
25548 KB |
Output is correct |
4 |
Correct |
243 ms |
25620 KB |
Output is correct |
5 |
Correct |
217 ms |
25564 KB |
Output is correct |
6 |
Correct |
209 ms |
25764 KB |
Output is correct |
7 |
Correct |
251 ms |
25804 KB |
Output is correct |
8 |
Correct |
238 ms |
25700 KB |
Output is correct |
9 |
Correct |
227 ms |
25696 KB |
Output is correct |
10 |
Correct |
225 ms |
25696 KB |
Output is correct |
11 |
Correct |
81 ms |
20560 KB |
Output is correct |
12 |
Correct |
210 ms |
25656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15704 KB |
Output is correct |
2 |
Correct |
4 ms |
14408 KB |
Output is correct |
3 |
Correct |
3 ms |
14172 KB |
Output is correct |
4 |
Correct |
13 ms |
17048 KB |
Output is correct |
5 |
Correct |
8 ms |
15708 KB |
Output is correct |
6 |
Correct |
4 ms |
14428 KB |
Output is correct |
7 |
Correct |
4 ms |
14428 KB |
Output is correct |
8 |
Correct |
4 ms |
14428 KB |
Output is correct |
9 |
Correct |
3 ms |
14428 KB |
Output is correct |
10 |
Correct |
8 ms |
15704 KB |
Output is correct |
11 |
Correct |
3 ms |
14168 KB |
Output is correct |
12 |
Correct |
3 ms |
14172 KB |
Output is correct |
13 |
Correct |
3 ms |
14172 KB |
Output is correct |
14 |
Correct |
3 ms |
14428 KB |
Output is correct |
15 |
Correct |
4 ms |
14424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
25676 KB |
Output is correct |
2 |
Correct |
206 ms |
25660 KB |
Output is correct |
3 |
Correct |
200 ms |
26544 KB |
Output is correct |
4 |
Correct |
240 ms |
25648 KB |
Output is correct |
5 |
Correct |
200 ms |
25668 KB |
Output is correct |
6 |
Correct |
202 ms |
25892 KB |
Output is correct |
7 |
Correct |
223 ms |
25640 KB |
Output is correct |
8 |
Correct |
214 ms |
25600 KB |
Output is correct |
9 |
Correct |
196 ms |
25416 KB |
Output is correct |
10 |
Correct |
155 ms |
25372 KB |
Output is correct |
11 |
Correct |
72 ms |
20336 KB |
Output is correct |
12 |
Correct |
206 ms |
25296 KB |
Output is correct |
13 |
Correct |
222 ms |
25548 KB |
Output is correct |
14 |
Correct |
219 ms |
25544 KB |
Output is correct |
15 |
Correct |
226 ms |
25548 KB |
Output is correct |
16 |
Correct |
243 ms |
25620 KB |
Output is correct |
17 |
Correct |
217 ms |
25564 KB |
Output is correct |
18 |
Correct |
209 ms |
25764 KB |
Output is correct |
19 |
Correct |
251 ms |
25804 KB |
Output is correct |
20 |
Correct |
238 ms |
25700 KB |
Output is correct |
21 |
Correct |
227 ms |
25696 KB |
Output is correct |
22 |
Correct |
225 ms |
25696 KB |
Output is correct |
23 |
Correct |
81 ms |
20560 KB |
Output is correct |
24 |
Correct |
210 ms |
25656 KB |
Output is correct |
25 |
Correct |
11 ms |
15704 KB |
Output is correct |
26 |
Correct |
4 ms |
14408 KB |
Output is correct |
27 |
Correct |
3 ms |
14172 KB |
Output is correct |
28 |
Correct |
13 ms |
17048 KB |
Output is correct |
29 |
Correct |
8 ms |
15708 KB |
Output is correct |
30 |
Correct |
4 ms |
14428 KB |
Output is correct |
31 |
Correct |
4 ms |
14428 KB |
Output is correct |
32 |
Correct |
4 ms |
14428 KB |
Output is correct |
33 |
Correct |
3 ms |
14428 KB |
Output is correct |
34 |
Correct |
8 ms |
15704 KB |
Output is correct |
35 |
Correct |
3 ms |
14168 KB |
Output is correct |
36 |
Correct |
3 ms |
14172 KB |
Output is correct |
37 |
Correct |
3 ms |
14172 KB |
Output is correct |
38 |
Correct |
3 ms |
14428 KB |
Output is correct |
39 |
Correct |
4 ms |
14424 KB |
Output is correct |
40 |
Correct |
199 ms |
25152 KB |
Output is correct |
41 |
Correct |
192 ms |
25292 KB |
Output is correct |
42 |
Correct |
242 ms |
25664 KB |
Output is correct |
43 |
Correct |
80 ms |
20564 KB |
Output is correct |
44 |
Correct |
71 ms |
20412 KB |
Output is correct |
45 |
Correct |
173 ms |
25608 KB |
Output is correct |
46 |
Correct |
195 ms |
25620 KB |
Output is correct |
47 |
Correct |
193 ms |
25676 KB |
Output is correct |
48 |
Correct |
87 ms |
20560 KB |
Output is correct |
49 |
Correct |
178 ms |
25788 KB |
Output is correct |
50 |
Correct |
176 ms |
25556 KB |
Output is correct |
51 |
Correct |
169 ms |
25644 KB |
Output is correct |