1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <iostream>
#include <queue>
#include <vector>
#define INF 2100000000;
using namespace std;
int n, m, v1,v2, fromOne[801], fromV1[801], fromV2[801];
vector<pair<int, int>> e[801];
priority_queue<pair<int, int>> q;
int getAns();
void dijkstra(int* from, int c);
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
e[a].push_back({ b, c });
e[b].push_back({ a, c });
}
cin >> v1 >> v2;
cout << getAns();
}
int getAns() {
dijkstra(fromOne, 1);
dijkstra(fromV1, v1);
dijkstra(fromV2, v2);
int ans = INF;
if (fromOne[v1] == ans || fromV1[v2] == ans || fromV1[n] == ans || fromV2[n] == ans)
return -1;
return min(fromOne[v1] + fromV1[v2] + fromV2[n], fromOne[v2] + fromV2[v1] + fromV1[n]);
}
void dijkstra(int* from, int c) {
for (int i = 1; i <= n; i++)
from[i] = INF;
from[c] = 0;
q.push({ 0, c });
while (!q.empty()) {
int cost = -q.top().first, cur = q.top().second;
q.pop();
if (cost > from[cur])
continue;
for (int i = 0; i < e[cur].size(); i++) {
int nc = cost + e[cur][i].second, next = e[cur][i].first;
if (nc < from[next]) {
from[next] = nc;
q.push({ -nc, next });
}
}
}
}
|
