#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
using namespace std;
#define pb push_back
#define pp pop_back
#define f first
#define s second
#define mp make_pair
const int N = (int) 1e6 + 123;
int n, m;
int S, T, U, V;
int edgeFrom[N];
int edgeTo[N];
int edgeWeight[N];
vector<int> g[N];
vector<int> dag[N];
long long d[4][N];
void dijkstra(long long *dist, int start) {
for (int i = 1; i <= n; i++) dist[i] = (long long) 1e18;
dist[start] = 0;
set<pair<long long, int>> s;
s.insert(make_pair(0, start));
while (!s.empty()) {
int v = s.begin() -> second;
s.erase(s.begin());
for (int edge : g[v]) {
int to = ((edgeFrom[edge] ^ edgeTo[edge]) ^ v);
if (dist[to] > dist[v] + edgeWeight[edge]) {
s.erase(make_pair(dist[to], to));
dist[to] = dist[v] + edgeWeight[edge];
s.insert(make_pair(dist[to], to));
}
}
}
}
bool used[N];
long long minU[N];
long long minV[N];
long long ans = 1e18;
void dfs(int v) {
if (used[v]) return;
used[v] = true;
minU[v] = d[2][v];
minV[v] = d[3][v];
for (auto to : dag[v]) {
dfs(to);
minU[v] = min(minU[v], minU[to]);
minV[v] = min(minV[v], minV[to]);
}
ans = min(ans, d[2][v] + minV[v]);
ans = min(ans, d[3][v] + minU[v]);
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
cin >> S >> T;
cin >> U >> V;
for (int i = 1; i <= m; i++) {
cin >> edgeFrom[i] >> edgeTo[i] >> edgeWeight[i];
g[edgeFrom[i]].push_back(i);
g[edgeTo[i]].push_back(i);
}
dijkstra(d[0], S);
dijkstra(d[1], T);
dijkstra(d[2], U);
dijkstra(d[3], V);
long long shortest = d[0][T];
for (int i = 1; i <= m; i++) {
if (d[0][edgeFrom[i]] + edgeWeight[i] + d[1][edgeTo[i]] == shortest) {
dag[edgeFrom[i]].push_back(edgeTo[i]);
} else if (d[0][edgeTo[i]] + edgeWeight[i] + d[1][edgeFrom[i]] == shortest) {
dag[edgeTo[i]].push_back(edgeFrom[i]);
}
}
dfs(S);
cout << min(ans, d[2][V]);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
491 ms |
60376 KB |
Output is correct |
2 |
Correct |
448 ms |
61048 KB |
Output is correct |
3 |
Correct |
439 ms |
64836 KB |
Output is correct |
4 |
Correct |
484 ms |
60536 KB |
Output is correct |
5 |
Correct |
396 ms |
61000 KB |
Output is correct |
6 |
Correct |
533 ms |
60544 KB |
Output is correct |
7 |
Correct |
443 ms |
60972 KB |
Output is correct |
8 |
Correct |
430 ms |
61180 KB |
Output is correct |
9 |
Correct |
444 ms |
59480 KB |
Output is correct |
10 |
Correct |
329 ms |
59556 KB |
Output is correct |
11 |
Correct |
150 ms |
60328 KB |
Output is correct |
12 |
Correct |
471 ms |
59228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
502 ms |
63136 KB |
Output is correct |
2 |
Correct |
476 ms |
62768 KB |
Output is correct |
3 |
Correct |
485 ms |
62416 KB |
Output is correct |
4 |
Correct |
470 ms |
66060 KB |
Output is correct |
5 |
Correct |
480 ms |
66628 KB |
Output is correct |
6 |
Correct |
437 ms |
68240 KB |
Output is correct |
7 |
Correct |
453 ms |
68416 KB |
Output is correct |
8 |
Correct |
497 ms |
66232 KB |
Output is correct |
9 |
Correct |
484 ms |
66596 KB |
Output is correct |
10 |
Correct |
494 ms |
65980 KB |
Output is correct |
11 |
Correct |
157 ms |
64396 KB |
Output is correct |
12 |
Correct |
433 ms |
68540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
47940 KB |
Output is correct |
2 |
Correct |
25 ms |
47372 KB |
Output is correct |
3 |
Correct |
29 ms |
47412 KB |
Output is correct |
4 |
Correct |
36 ms |
49268 KB |
Output is correct |
5 |
Correct |
34 ms |
48228 KB |
Output is correct |
6 |
Correct |
27 ms |
47564 KB |
Output is correct |
7 |
Correct |
34 ms |
47464 KB |
Output is correct |
8 |
Correct |
31 ms |
47564 KB |
Output is correct |
9 |
Correct |
25 ms |
47564 KB |
Output is correct |
10 |
Correct |
31 ms |
48324 KB |
Output is correct |
11 |
Correct |
28 ms |
47296 KB |
Output is correct |
12 |
Correct |
30 ms |
47304 KB |
Output is correct |
13 |
Correct |
24 ms |
47340 KB |
Output is correct |
14 |
Correct |
24 ms |
47308 KB |
Output is correct |
15 |
Correct |
33 ms |
47432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
491 ms |
60376 KB |
Output is correct |
2 |
Correct |
448 ms |
61048 KB |
Output is correct |
3 |
Correct |
439 ms |
64836 KB |
Output is correct |
4 |
Correct |
484 ms |
60536 KB |
Output is correct |
5 |
Correct |
396 ms |
61000 KB |
Output is correct |
6 |
Correct |
533 ms |
60544 KB |
Output is correct |
7 |
Correct |
443 ms |
60972 KB |
Output is correct |
8 |
Correct |
430 ms |
61180 KB |
Output is correct |
9 |
Correct |
444 ms |
59480 KB |
Output is correct |
10 |
Correct |
329 ms |
59556 KB |
Output is correct |
11 |
Correct |
150 ms |
60328 KB |
Output is correct |
12 |
Correct |
471 ms |
59228 KB |
Output is correct |
13 |
Correct |
502 ms |
63136 KB |
Output is correct |
14 |
Correct |
476 ms |
62768 KB |
Output is correct |
15 |
Correct |
485 ms |
62416 KB |
Output is correct |
16 |
Correct |
470 ms |
66060 KB |
Output is correct |
17 |
Correct |
480 ms |
66628 KB |
Output is correct |
18 |
Correct |
437 ms |
68240 KB |
Output is correct |
19 |
Correct |
453 ms |
68416 KB |
Output is correct |
20 |
Correct |
497 ms |
66232 KB |
Output is correct |
21 |
Correct |
484 ms |
66596 KB |
Output is correct |
22 |
Correct |
494 ms |
65980 KB |
Output is correct |
23 |
Correct |
157 ms |
64396 KB |
Output is correct |
24 |
Correct |
433 ms |
68540 KB |
Output is correct |
25 |
Correct |
40 ms |
47940 KB |
Output is correct |
26 |
Correct |
25 ms |
47372 KB |
Output is correct |
27 |
Correct |
29 ms |
47412 KB |
Output is correct |
28 |
Correct |
36 ms |
49268 KB |
Output is correct |
29 |
Correct |
34 ms |
48228 KB |
Output is correct |
30 |
Correct |
27 ms |
47564 KB |
Output is correct |
31 |
Correct |
34 ms |
47464 KB |
Output is correct |
32 |
Correct |
31 ms |
47564 KB |
Output is correct |
33 |
Correct |
25 ms |
47564 KB |
Output is correct |
34 |
Correct |
31 ms |
48324 KB |
Output is correct |
35 |
Correct |
28 ms |
47296 KB |
Output is correct |
36 |
Correct |
30 ms |
47304 KB |
Output is correct |
37 |
Correct |
24 ms |
47340 KB |
Output is correct |
38 |
Correct |
24 ms |
47308 KB |
Output is correct |
39 |
Correct |
33 ms |
47432 KB |
Output is correct |
40 |
Correct |
525 ms |
67180 KB |
Output is correct |
41 |
Correct |
490 ms |
63908 KB |
Output is correct |
42 |
Correct |
460 ms |
63812 KB |
Output is correct |
43 |
Correct |
157 ms |
64828 KB |
Output is correct |
44 |
Correct |
187 ms |
64872 KB |
Output is correct |
45 |
Correct |
367 ms |
64836 KB |
Output is correct |
46 |
Correct |
368 ms |
64580 KB |
Output is correct |
47 |
Correct |
487 ms |
64976 KB |
Output is correct |
48 |
Correct |
164 ms |
62220 KB |
Output is correct |
49 |
Correct |
351 ms |
66992 KB |
Output is correct |
50 |
Correct |
383 ms |
64296 KB |
Output is correct |
51 |
Correct |
361 ms |
64956 KB |
Output is correct |