#include <bits/stdc++.h>
using namespace std;
const int DIM = 100005;
long long dst1[DIM], dst2[DIM];
vector<pair<int, int>> edg[DIM];
pair<long long, long long> dp[DIM][4];
void dijkstra(int s, int n, long long dst[DIM]) {
static priority_queue<pair<long long, int>,
vector<pair<long long, int>>,
greater<pair<long long, int>>> prq;
for (int i = 1; i <= n; ++i) {
dst[i] = (1LL << 50); }
dst[s] = 0; prq.push(make_pair(0, s));
while (prq.size()) {
long long d = prq.top().first;
int x = prq.top().second; prq.pop();
if (dst[x] != d) {
continue; }
for (auto &ed : edg[x]) {
int y = ed.first, c = ed.second;
if (dst[y] > dst[x] + c) {
dst[y] = dst[x] + c;
prq.push(make_pair(dst[y], y)); } } } }
int main(void) {
#ifdef HOME
freopen("commuter.in", "r", stdin);
freopen("commuter.out", "w", stdout);
#endif
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for (int i = 1; i <= m; ++i) {
int x, y, c; cin >> x >> y >> c;
edg[x].push_back(make_pair(y, c));
edg[y].push_back(make_pair(x, c)); }
dijkstra(u, n, dst1); dijkstra(v, n, dst2);
priority_queue<pair<pair<long long, long long>, pair<int, int>>,
vector<pair<pair<long long, long long>, pair<int, int>>>,
greater<pair<pair<long long, long long>, pair<int, int>>>> prq;
for (int i = 1; i <= n; ++i) {
for (int k = 0; k <= 3; ++k) {
dp[i][k] = make_pair(1LL << 50, 1LL << 50); } }
dp[s][0] = make_pair(0LL, 0LL); prq.push(make_pair(make_pair(0LL, 0LL), make_pair(s, 0)));
while (prq.size()) {
pair<long long, long long> d = prq.top().first;
int x = prq.top().second.first, k = prq.top().second.second; prq.pop();
if (dp[x][k] != d) {
continue; }
if (!(k & 1) and dp[x][k ^ 1] > make_pair(dp[x][k].first, dp[x][k].second + dst1[x])) {
dp[x][k ^ 1] = make_pair(dp[x][k].first, dp[x][k].second + dst1[x]);
prq.push(make_pair(dp[x][k ^ 1], make_pair(x, k ^ 1))); }
if (!(k & 2) and dp[x][k ^ 2] > make_pair(dp[x][k].first, dp[x][k].second + dst2[x])) {
dp[x][k ^ 2] = make_pair(dp[x][k].first, dp[x][k].second + dst2[x]);
prq.push(make_pair(dp[x][k ^ 2], make_pair(x, k ^ 2))); }
for (auto &ed : edg[x]) {
int y = ed.first, c = ed.second;
if (dp[y][k] > make_pair(dp[x][k].first + c, dp[x][k].second)) {
dp[y][k] = make_pair(dp[x][k].first + c, dp[x][k].second);
prq.push(make_pair(dp[y][k], make_pair(y, k))); } } }
cout << min(dp[t][3].second, dst1[v]);
return 0; }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
697 ms |
35544 KB |
Output is correct |
2 |
Correct |
827 ms |
35544 KB |
Output is correct |
3 |
Correct |
808 ms |
35772 KB |
Output is correct |
4 |
Correct |
698 ms |
40896 KB |
Output is correct |
5 |
Correct |
743 ms |
43172 KB |
Output is correct |
6 |
Correct |
712 ms |
54268 KB |
Output is correct |
7 |
Correct |
687 ms |
54268 KB |
Output is correct |
8 |
Correct |
674 ms |
54268 KB |
Output is correct |
9 |
Correct |
752 ms |
58256 KB |
Output is correct |
10 |
Correct |
637 ms |
62764 KB |
Output is correct |
11 |
Correct |
263 ms |
62764 KB |
Output is correct |
12 |
Correct |
730 ms |
69156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
861 ms |
73128 KB |
Output is correct |
2 |
Correct |
797 ms |
76412 KB |
Output is correct |
3 |
Correct |
820 ms |
79952 KB |
Output is correct |
4 |
Correct |
832 ms |
83348 KB |
Output is correct |
5 |
Correct |
816 ms |
86828 KB |
Output is correct |
6 |
Correct |
782 ms |
90396 KB |
Output is correct |
7 |
Correct |
906 ms |
93924 KB |
Output is correct |
8 |
Correct |
844 ms |
97384 KB |
Output is correct |
9 |
Correct |
839 ms |
100904 KB |
Output is correct |
10 |
Correct |
817 ms |
104384 KB |
Output is correct |
11 |
Correct |
378 ms |
104384 KB |
Output is correct |
12 |
Correct |
702 ms |
110032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
110032 KB |
Output is correct |
2 |
Correct |
5 ms |
110032 KB |
Output is correct |
3 |
Correct |
5 ms |
110032 KB |
Output is correct |
4 |
Correct |
65 ms |
110032 KB |
Output is correct |
5 |
Correct |
29 ms |
110032 KB |
Output is correct |
6 |
Correct |
7 ms |
110032 KB |
Output is correct |
7 |
Correct |
8 ms |
110032 KB |
Output is correct |
8 |
Correct |
8 ms |
110032 KB |
Output is correct |
9 |
Correct |
7 ms |
110032 KB |
Output is correct |
10 |
Correct |
28 ms |
110032 KB |
Output is correct |
11 |
Correct |
5 ms |
110032 KB |
Output is correct |
12 |
Correct |
4 ms |
110032 KB |
Output is correct |
13 |
Correct |
6 ms |
110032 KB |
Output is correct |
14 |
Correct |
5 ms |
110032 KB |
Output is correct |
15 |
Correct |
6 ms |
110032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
697 ms |
35544 KB |
Output is correct |
2 |
Correct |
827 ms |
35544 KB |
Output is correct |
3 |
Correct |
808 ms |
35772 KB |
Output is correct |
4 |
Correct |
698 ms |
40896 KB |
Output is correct |
5 |
Correct |
743 ms |
43172 KB |
Output is correct |
6 |
Correct |
712 ms |
54268 KB |
Output is correct |
7 |
Correct |
687 ms |
54268 KB |
Output is correct |
8 |
Correct |
674 ms |
54268 KB |
Output is correct |
9 |
Correct |
752 ms |
58256 KB |
Output is correct |
10 |
Correct |
637 ms |
62764 KB |
Output is correct |
11 |
Correct |
263 ms |
62764 KB |
Output is correct |
12 |
Correct |
730 ms |
69156 KB |
Output is correct |
13 |
Correct |
861 ms |
73128 KB |
Output is correct |
14 |
Correct |
797 ms |
76412 KB |
Output is correct |
15 |
Correct |
820 ms |
79952 KB |
Output is correct |
16 |
Correct |
832 ms |
83348 KB |
Output is correct |
17 |
Correct |
816 ms |
86828 KB |
Output is correct |
18 |
Correct |
782 ms |
90396 KB |
Output is correct |
19 |
Correct |
906 ms |
93924 KB |
Output is correct |
20 |
Correct |
844 ms |
97384 KB |
Output is correct |
21 |
Correct |
839 ms |
100904 KB |
Output is correct |
22 |
Correct |
817 ms |
104384 KB |
Output is correct |
23 |
Correct |
378 ms |
104384 KB |
Output is correct |
24 |
Correct |
702 ms |
110032 KB |
Output is correct |
25 |
Correct |
35 ms |
110032 KB |
Output is correct |
26 |
Correct |
5 ms |
110032 KB |
Output is correct |
27 |
Correct |
5 ms |
110032 KB |
Output is correct |
28 |
Correct |
65 ms |
110032 KB |
Output is correct |
29 |
Correct |
29 ms |
110032 KB |
Output is correct |
30 |
Correct |
7 ms |
110032 KB |
Output is correct |
31 |
Correct |
8 ms |
110032 KB |
Output is correct |
32 |
Correct |
8 ms |
110032 KB |
Output is correct |
33 |
Correct |
7 ms |
110032 KB |
Output is correct |
34 |
Correct |
28 ms |
110032 KB |
Output is correct |
35 |
Correct |
5 ms |
110032 KB |
Output is correct |
36 |
Correct |
4 ms |
110032 KB |
Output is correct |
37 |
Correct |
6 ms |
110032 KB |
Output is correct |
38 |
Correct |
5 ms |
110032 KB |
Output is correct |
39 |
Correct |
6 ms |
110032 KB |
Output is correct |
40 |
Correct |
737 ms |
123696 KB |
Output is correct |
41 |
Correct |
713 ms |
123696 KB |
Output is correct |
42 |
Correct |
795 ms |
125096 KB |
Output is correct |
43 |
Correct |
301 ms |
125096 KB |
Output is correct |
44 |
Correct |
293 ms |
125096 KB |
Output is correct |
45 |
Correct |
759 ms |
132660 KB |
Output is correct |
46 |
Correct |
801 ms |
135616 KB |
Output is correct |
47 |
Correct |
832 ms |
140788 KB |
Output is correct |
48 |
Correct |
356 ms |
140788 KB |
Output is correct |
49 |
Correct |
673 ms |
152468 KB |
Output is correct |
50 |
Correct |
620 ms |
152468 KB |
Output is correct |
51 |
Correct |
669 ms |
152468 KB |
Output is correct |