#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
ll n, m;
ll d[N][4], dis[N];
vector<pair<ll, ll>> node[N];
void dijk(ll u, ll t){
for (int i = 1; i <= n; i++) d[i][t] = 1e18;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, u});
d[u][t] = 0;
while (pq.size()){
pair<ll, ll> x = pq.top();
pq.pop();
if (x.first != d[x.second][t]) continue;
for (auto j : node[x.second]){
if (d[j.first][t] > (x.first + j.second)){
d[j.first][t] = x.first + j.second;
pq.push({d[j.first][t], j.first});
}
}
}
/*
cout << u << ": ";
for (int i = 1; i <= n; i++){
cout << d[i][t] << " ";
}
cout << endl;
*/
}
bool cmp(ll u, ll v){
return d[u][0] < d[v][0];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("balance.in", "r")){
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
}
cin >> n >> m;
ll s, t, u, v;
cin >> s >> t >> u >> v;
for (int i = 1; i <= m; i++){
ll u, v, c;
cin >> u >> v >> c;
node[u].push_back({v, c});
node[v].push_back({u, c});
}
dijk(s, 0);
dijk(t, 1);
dijk(u, 2);
dijk(v, 3);
ll lim = d[t][0];
ll ans = 1e18;
vector<ll> now;
for (int i = 1; i <= n; i++){
now.push_back(i);
dis[i] = d[i][2];
}
sort(now.begin(), now.end(), cmp);
for (int i = 1; i <= n; i++){
ll x = now[i - 1];
//cout << x << ": ";
for (auto j : node[x]){
//cout << j.first << " " << d[x][0] << " " << j.second << " " << d[j.first][1] << endl;
if ((d[x][0] + j.second + d[j.first][1]) == lim){
dis[j.first] = min(dis[j.first], dis[x]);
}
}
//cout << endl;
//cout << dis[x] << " " << d[x][3] << " " << x << endl;
ans = min(ans, dis[x] + d[x][3]);
}
now.clear();
for (int i = 1; i <= n; i++){
now.push_back(i);
dis[i] = d[i][3];
}
sort(now.begin(), now.end(), cmp);
for (int i = 1; i <= n; i++){
ll x = now[i - 1];
for (auto j : node[x]){
if ((d[x][0] + j.second + d[j.first][1]) == lim){
dis[j.first] = min(dis[j.first], dis[x]);
}
}
ans = min(ans, dis[x] + d[x][2]);
}
cout << ans;
}
/*
*/
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:42:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
42 | freopen("balance.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:43:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
43 | freopen("balance.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
488 ms |
23236 KB |
Output is correct |
2 |
Correct |
475 ms |
22284 KB |
Output is correct |
3 |
Correct |
473 ms |
23028 KB |
Output is correct |
4 |
Correct |
467 ms |
23032 KB |
Output is correct |
5 |
Correct |
444 ms |
22348 KB |
Output is correct |
6 |
Correct |
474 ms |
23276 KB |
Output is correct |
7 |
Correct |
485 ms |
22200 KB |
Output is correct |
8 |
Correct |
485 ms |
22168 KB |
Output is correct |
9 |
Correct |
460 ms |
23148 KB |
Output is correct |
10 |
Correct |
385 ms |
23400 KB |
Output is correct |
11 |
Correct |
208 ms |
14828 KB |
Output is correct |
12 |
Correct |
484 ms |
23156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
480 ms |
22448 KB |
Output is correct |
2 |
Correct |
519 ms |
22256 KB |
Output is correct |
3 |
Correct |
480 ms |
22264 KB |
Output is correct |
4 |
Correct |
482 ms |
22248 KB |
Output is correct |
5 |
Correct |
478 ms |
22268 KB |
Output is correct |
6 |
Correct |
457 ms |
22444 KB |
Output is correct |
7 |
Correct |
493 ms |
22256 KB |
Output is correct |
8 |
Correct |
520 ms |
22240 KB |
Output is correct |
9 |
Correct |
544 ms |
22256 KB |
Output is correct |
10 |
Correct |
519 ms |
22424 KB |
Output is correct |
11 |
Correct |
228 ms |
14836 KB |
Output is correct |
12 |
Correct |
532 ms |
22484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
4352 KB |
Output is correct |
2 |
Correct |
3 ms |
2688 KB |
Output is correct |
3 |
Correct |
3 ms |
2816 KB |
Output is correct |
4 |
Correct |
20 ms |
6136 KB |
Output is correct |
5 |
Correct |
10 ms |
4352 KB |
Output is correct |
6 |
Correct |
3 ms |
2816 KB |
Output is correct |
7 |
Correct |
3 ms |
2816 KB |
Output is correct |
8 |
Correct |
4 ms |
2944 KB |
Output is correct |
9 |
Correct |
4 ms |
2816 KB |
Output is correct |
10 |
Correct |
10 ms |
4352 KB |
Output is correct |
11 |
Correct |
4 ms |
2688 KB |
Output is correct |
12 |
Correct |
2 ms |
2688 KB |
Output is correct |
13 |
Correct |
3 ms |
2816 KB |
Output is correct |
14 |
Correct |
3 ms |
2816 KB |
Output is correct |
15 |
Correct |
3 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
488 ms |
23236 KB |
Output is correct |
2 |
Correct |
475 ms |
22284 KB |
Output is correct |
3 |
Correct |
473 ms |
23028 KB |
Output is correct |
4 |
Correct |
467 ms |
23032 KB |
Output is correct |
5 |
Correct |
444 ms |
22348 KB |
Output is correct |
6 |
Correct |
474 ms |
23276 KB |
Output is correct |
7 |
Correct |
485 ms |
22200 KB |
Output is correct |
8 |
Correct |
485 ms |
22168 KB |
Output is correct |
9 |
Correct |
460 ms |
23148 KB |
Output is correct |
10 |
Correct |
385 ms |
23400 KB |
Output is correct |
11 |
Correct |
208 ms |
14828 KB |
Output is correct |
12 |
Correct |
484 ms |
23156 KB |
Output is correct |
13 |
Correct |
480 ms |
22448 KB |
Output is correct |
14 |
Correct |
519 ms |
22256 KB |
Output is correct |
15 |
Correct |
480 ms |
22264 KB |
Output is correct |
16 |
Correct |
482 ms |
22248 KB |
Output is correct |
17 |
Correct |
478 ms |
22268 KB |
Output is correct |
18 |
Correct |
457 ms |
22444 KB |
Output is correct |
19 |
Correct |
493 ms |
22256 KB |
Output is correct |
20 |
Correct |
520 ms |
22240 KB |
Output is correct |
21 |
Correct |
544 ms |
22256 KB |
Output is correct |
22 |
Correct |
519 ms |
22424 KB |
Output is correct |
23 |
Correct |
228 ms |
14836 KB |
Output is correct |
24 |
Correct |
532 ms |
22484 KB |
Output is correct |
25 |
Correct |
11 ms |
4352 KB |
Output is correct |
26 |
Correct |
3 ms |
2688 KB |
Output is correct |
27 |
Correct |
3 ms |
2816 KB |
Output is correct |
28 |
Correct |
20 ms |
6136 KB |
Output is correct |
29 |
Correct |
10 ms |
4352 KB |
Output is correct |
30 |
Correct |
3 ms |
2816 KB |
Output is correct |
31 |
Correct |
3 ms |
2816 KB |
Output is correct |
32 |
Correct |
4 ms |
2944 KB |
Output is correct |
33 |
Correct |
4 ms |
2816 KB |
Output is correct |
34 |
Correct |
10 ms |
4352 KB |
Output is correct |
35 |
Correct |
4 ms |
2688 KB |
Output is correct |
36 |
Correct |
2 ms |
2688 KB |
Output is correct |
37 |
Correct |
3 ms |
2816 KB |
Output is correct |
38 |
Correct |
3 ms |
2816 KB |
Output is correct |
39 |
Correct |
3 ms |
2816 KB |
Output is correct |
40 |
Correct |
485 ms |
23288 KB |
Output is correct |
41 |
Correct |
465 ms |
23080 KB |
Output is correct |
42 |
Correct |
467 ms |
23196 KB |
Output is correct |
43 |
Correct |
239 ms |
14832 KB |
Output is correct |
44 |
Correct |
228 ms |
14960 KB |
Output is correct |
45 |
Correct |
425 ms |
22176 KB |
Output is correct |
46 |
Correct |
425 ms |
22048 KB |
Output is correct |
47 |
Correct |
454 ms |
23116 KB |
Output is correct |
48 |
Correct |
254 ms |
14296 KB |
Output is correct |
49 |
Correct |
381 ms |
22900 KB |
Output is correct |
50 |
Correct |
438 ms |
22192 KB |
Output is correct |
51 |
Correct |
422 ms |
22168 KB |
Output is correct |