/**
。∠(*・ω・)っ ⌒ 由 ~ (( ,,・з・,, ))
_Π_____。
/______/~\
| 田田|門|
**/
#include <bits/stdc++.h>
using namespace std;
#define fori(i, l, r) for(int (i) = (l); i < (r); ++i)
#define forie(i, l, r) for (int (i) = (l); i <= (r); ++i)
#define ford(i, l, r) for (int (i) = (l); i > (r); --i)
#define forde(i, l, r) for (int (i) = (l); i >= (r); --i)
#define int long long
#define i_inf INT_MAX
#define inf LLONG_MAX
#define ii pair<int,int>
#define fi first
#define se second
#define gcd __gcd
#define lcm(x,y) x * y/ gcd(x,y)
#define pb push_back
#define sz size
#define all(x) begin(x), end(x)
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr);
#define el "\n"
#define sp " "
//
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
// var declare
const int maxn = 2e5 + 3;
int n, m, S, T, U, V;
// ds declare
vector <ii> adj[maxn];
//
vector <int> dijkstra(int s)
{
vector <int> dist(n, inf);
priority_queue<ii, vector<ii>, greater<ii>> pq;
dist[s] = 0;
pq.push({0, s});
while (pq.sz())
{
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w]: adj[u])
{
if (dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
//
int commuter_pass(int S, int T)
{
auto fromS = dijkstra(S);
auto fromT = dijkstra(T);
auto fromU = dijkstra(U);
auto fromV = dijkstra(V);
vector <int> f(n, inf);
vector <int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int x, int y){
return fromS[x] < fromS[y];
});
int ans = fromU[V];
for (auto u: order)
{
f[u] = min(f[u], fromU[u]);
for (auto [v, w]: adj[u])
{
if (fromS[u] + w == fromS[v] && fromS[u] + w + fromT[v] == fromS[T])
{
f[v] = min(f[v], f[u]);
}
}
if (fromS[u] + fromT[u] == fromS[T])
ans = min(ans, f[u] + fromV[u]);
}
return ans;
}
//
void solve()
{
cin >> n >> m;
cin >> S >> T >> U >> V;
--S, --T, --U, --V;
forie(i, 1, m)
{
int u, v, w; cin >> u >> v >> w;
--u, --v;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
cout << min(commuter_pass(S, T), commuter_pass(T, S));
}
//
void multi_test()
{
int t;
cin >> t;
while (t--) solve();
}
//
int32_t main()
{
fastio;
solve();
return 0;
}
/**
**/
Compilation message
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:13:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
13 | #define forie(i, l, r) for (int (i) = (l); i <= (r); ++i)
| ^
commuter_pass.cpp:96:2: note: in expansion of macro 'forie'
96 | forie(i, 1, m)
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
348 ms |
21836 KB |
Output is correct |
2 |
Correct |
338 ms |
23968 KB |
Output is correct |
3 |
Correct |
349 ms |
24236 KB |
Output is correct |
4 |
Correct |
300 ms |
25524 KB |
Output is correct |
5 |
Correct |
323 ms |
24088 KB |
Output is correct |
6 |
Correct |
361 ms |
25544 KB |
Output is correct |
7 |
Correct |
322 ms |
24064 KB |
Output is correct |
8 |
Correct |
311 ms |
23924 KB |
Output is correct |
9 |
Correct |
354 ms |
25092 KB |
Output is correct |
10 |
Correct |
228 ms |
24660 KB |
Output is correct |
11 |
Correct |
101 ms |
16996 KB |
Output is correct |
12 |
Correct |
326 ms |
24676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
374 ms |
20504 KB |
Output is correct |
2 |
Correct |
371 ms |
24076 KB |
Output is correct |
3 |
Correct |
371 ms |
23844 KB |
Output is correct |
4 |
Correct |
366 ms |
24336 KB |
Output is correct |
5 |
Correct |
326 ms |
24004 KB |
Output is correct |
6 |
Correct |
325 ms |
24092 KB |
Output is correct |
7 |
Correct |
348 ms |
23948 KB |
Output is correct |
8 |
Correct |
366 ms |
24212 KB |
Output is correct |
9 |
Correct |
329 ms |
24000 KB |
Output is correct |
10 |
Correct |
362 ms |
24308 KB |
Output is correct |
11 |
Correct |
107 ms |
17232 KB |
Output is correct |
12 |
Correct |
317 ms |
24080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
5168 KB |
Output is correct |
4 |
Correct |
12 ms |
8536 KB |
Output is correct |
5 |
Correct |
7 ms |
6892 KB |
Output is correct |
6 |
Correct |
2 ms |
5212 KB |
Output is correct |
7 |
Correct |
2 ms |
5256 KB |
Output is correct |
8 |
Correct |
3 ms |
5212 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
7 ms |
6860 KB |
Output is correct |
11 |
Correct |
1 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
2 ms |
5164 KB |
Output is correct |
15 |
Correct |
2 ms |
5208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
348 ms |
21836 KB |
Output is correct |
2 |
Correct |
338 ms |
23968 KB |
Output is correct |
3 |
Correct |
349 ms |
24236 KB |
Output is correct |
4 |
Correct |
300 ms |
25524 KB |
Output is correct |
5 |
Correct |
323 ms |
24088 KB |
Output is correct |
6 |
Correct |
361 ms |
25544 KB |
Output is correct |
7 |
Correct |
322 ms |
24064 KB |
Output is correct |
8 |
Correct |
311 ms |
23924 KB |
Output is correct |
9 |
Correct |
354 ms |
25092 KB |
Output is correct |
10 |
Correct |
228 ms |
24660 KB |
Output is correct |
11 |
Correct |
101 ms |
16996 KB |
Output is correct |
12 |
Correct |
326 ms |
24676 KB |
Output is correct |
13 |
Correct |
374 ms |
20504 KB |
Output is correct |
14 |
Correct |
371 ms |
24076 KB |
Output is correct |
15 |
Correct |
371 ms |
23844 KB |
Output is correct |
16 |
Correct |
366 ms |
24336 KB |
Output is correct |
17 |
Correct |
326 ms |
24004 KB |
Output is correct |
18 |
Correct |
325 ms |
24092 KB |
Output is correct |
19 |
Correct |
348 ms |
23948 KB |
Output is correct |
20 |
Correct |
366 ms |
24212 KB |
Output is correct |
21 |
Correct |
329 ms |
24000 KB |
Output is correct |
22 |
Correct |
362 ms |
24308 KB |
Output is correct |
23 |
Correct |
107 ms |
17232 KB |
Output is correct |
24 |
Correct |
317 ms |
24080 KB |
Output is correct |
25 |
Correct |
7 ms |
6488 KB |
Output is correct |
26 |
Correct |
2 ms |
4956 KB |
Output is correct |
27 |
Correct |
2 ms |
5168 KB |
Output is correct |
28 |
Correct |
12 ms |
8536 KB |
Output is correct |
29 |
Correct |
7 ms |
6892 KB |
Output is correct |
30 |
Correct |
2 ms |
5212 KB |
Output is correct |
31 |
Correct |
2 ms |
5256 KB |
Output is correct |
32 |
Correct |
3 ms |
5212 KB |
Output is correct |
33 |
Correct |
2 ms |
5212 KB |
Output is correct |
34 |
Correct |
7 ms |
6860 KB |
Output is correct |
35 |
Correct |
1 ms |
4956 KB |
Output is correct |
36 |
Correct |
1 ms |
4956 KB |
Output is correct |
37 |
Correct |
2 ms |
5212 KB |
Output is correct |
38 |
Correct |
2 ms |
5164 KB |
Output is correct |
39 |
Correct |
2 ms |
5208 KB |
Output is correct |
40 |
Correct |
342 ms |
25496 KB |
Output is correct |
41 |
Correct |
309 ms |
24708 KB |
Output is correct |
42 |
Correct |
312 ms |
25040 KB |
Output is correct |
43 |
Correct |
96 ms |
17120 KB |
Output is correct |
44 |
Correct |
100 ms |
17192 KB |
Output is correct |
45 |
Correct |
285 ms |
23756 KB |
Output is correct |
46 |
Correct |
300 ms |
23372 KB |
Output is correct |
47 |
Correct |
330 ms |
25556 KB |
Output is correct |
48 |
Correct |
104 ms |
16580 KB |
Output is correct |
49 |
Correct |
267 ms |
25412 KB |
Output is correct |
50 |
Correct |
348 ms |
23832 KB |
Output is correct |
51 |
Correct |
250 ms |
23500 KB |
Output is correct |