#include <bits/stdc++.h>
using namespace std;
long long dp[100005][5], dist[100005];
vector <pair <int, int>> ke[100005];
pair <long long, long long> f[100005][5];
long long ans = LLONG_MAX;
int n, m, s[5];
struct lmt {
long long cost, sub;
int u, type;
bool operator < (const lmt other) const {
if (cost != other.cost)
return cost > other.cost;
return sub > other.sub;
}
};
priority_queue <lmt> qz;
void dijkstra(int id) {
for (int i = 1; i <= n; i++)
dist[i] = LLONG_MAX;
dist[s[id]] = 0;
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> q;
q.push({0, s[id]});
while (q.size()) {
long long now = q.top().first;
int u = q.top().second;
q.pop();
if (dist[u] != now)
continue;
for (pair <int, int> next : ke[u]) {
int v = next.first;
int w = next.second;
if (dist[v] > now + w) {
dist[v] = now + w;
q.push({dist[v], v});
}
}
}
for (int i = 1; i <= n; i++) {
dp[i][id - 2] = dist[i];
dp[i][2] += dist[i];
}
ans = min(ans, dist[s[id ^ 1]]);
}
void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 2; j++)
f[i][j] = {LLONG_MAX, dp[i][j]};
}
for (int j = 0; j <= 2; j++) {
f[s[0]][j] = {0, dp[s[0]][j]};
qz.push({0, dp[s[0]][j], s[0], j});
}
while (qz.size()) {
long long val = qz.top().cost;
long long to = qz.top().sub;
int u = qz.top().u;
int type = qz.top().type;
qz.pop();
if (f[u][type].first != val || f[u][type].second != to)
continue;
for (pair <int, int> next : ke[u]) {
int v = next.first;
int w = next.second;
if (val + w < f[v][type].first) {
f[v][type].first = val + w;
f[v][type].second = min(dp[v][type], f[u][type].second);
qz.push({f[v][type].first, f[v][type].second, v, type});
} else if (val + w == f[v][type].first) {
if (f[u][type].second < f[v][type].second) {
f[v][type].second = f[u][type].second;
qz.push({f[v][type].first, f[v][type].second, v, type});
}
}
if (type != 2) {
if (val + w < f[v][2].first) {
f[v][2].first = val + w;
f[v][2].second = f[u][type].second + min(dp[v][type ^ 1], dp[u][type ^ 1]);
qz.push({f[v][2].first, f[v][2].second, v, 2});
} else if (val + w == f[v][2].first) {
if (f[u][type].second + min(dp[v][type ^ 1], dp[u][type ^ 1]) < f[v][2].second) {
f[v][2].second = f[u][type].second + min(dp[v][type ^ 1], dp[u][type ^ 1]);
qz.push({f[v][2].first, f[v][2].second, v, 2});
}
}
}
}
}
ans = min(ans, f[s[1]][2].second);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("TASK.INP", "r", stdin);
// freopen("TASK.OUT", "w", stdout);
cin >> n >> m;
for (int i = 0; i <= 3; i++)
cin >> s[i];
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
ke[u].push_back({v, c});
ke[v].push_back({u, c});
}
dijkstra(2);
dijkstra(3);
solve();
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
317 ms |
37520 KB |
Output is correct |
2 |
Correct |
285 ms |
30028 KB |
Output is correct |
3 |
Correct |
281 ms |
29700 KB |
Output is correct |
4 |
Correct |
259 ms |
30792 KB |
Output is correct |
5 |
Correct |
229 ms |
30000 KB |
Output is correct |
6 |
Correct |
278 ms |
37048 KB |
Output is correct |
7 |
Correct |
259 ms |
30000 KB |
Output is correct |
8 |
Correct |
262 ms |
29484 KB |
Output is correct |
9 |
Correct |
263 ms |
30164 KB |
Output is correct |
10 |
Correct |
191 ms |
30248 KB |
Output is correct |
11 |
Correct |
64 ms |
18212 KB |
Output is correct |
12 |
Correct |
270 ms |
30968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
293 ms |
29380 KB |
Output is correct |
2 |
Correct |
262 ms |
30544 KB |
Output is correct |
3 |
Correct |
284 ms |
30816 KB |
Output is correct |
4 |
Correct |
262 ms |
30328 KB |
Output is correct |
5 |
Correct |
282 ms |
30444 KB |
Output is correct |
6 |
Correct |
243 ms |
27100 KB |
Output is correct |
7 |
Correct |
280 ms |
29620 KB |
Output is correct |
8 |
Correct |
261 ms |
30724 KB |
Output is correct |
9 |
Correct |
277 ms |
30056 KB |
Output is correct |
10 |
Correct |
284 ms |
29312 KB |
Output is correct |
11 |
Correct |
71 ms |
18260 KB |
Output is correct |
12 |
Correct |
239 ms |
30672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7704 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6488 KB |
Output is correct |
4 |
Correct |
12 ms |
8024 KB |
Output is correct |
5 |
Correct |
6 ms |
7260 KB |
Output is correct |
6 |
Correct |
2 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
6 ms |
7260 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
317 ms |
37520 KB |
Output is correct |
2 |
Correct |
285 ms |
30028 KB |
Output is correct |
3 |
Correct |
281 ms |
29700 KB |
Output is correct |
4 |
Correct |
259 ms |
30792 KB |
Output is correct |
5 |
Correct |
229 ms |
30000 KB |
Output is correct |
6 |
Correct |
278 ms |
37048 KB |
Output is correct |
7 |
Correct |
259 ms |
30000 KB |
Output is correct |
8 |
Correct |
262 ms |
29484 KB |
Output is correct |
9 |
Correct |
263 ms |
30164 KB |
Output is correct |
10 |
Correct |
191 ms |
30248 KB |
Output is correct |
11 |
Correct |
64 ms |
18212 KB |
Output is correct |
12 |
Correct |
270 ms |
30968 KB |
Output is correct |
13 |
Correct |
293 ms |
29380 KB |
Output is correct |
14 |
Correct |
262 ms |
30544 KB |
Output is correct |
15 |
Correct |
284 ms |
30816 KB |
Output is correct |
16 |
Correct |
262 ms |
30328 KB |
Output is correct |
17 |
Correct |
282 ms |
30444 KB |
Output is correct |
18 |
Correct |
243 ms |
27100 KB |
Output is correct |
19 |
Correct |
280 ms |
29620 KB |
Output is correct |
20 |
Correct |
261 ms |
30724 KB |
Output is correct |
21 |
Correct |
277 ms |
30056 KB |
Output is correct |
22 |
Correct |
284 ms |
29312 KB |
Output is correct |
23 |
Correct |
71 ms |
18260 KB |
Output is correct |
24 |
Correct |
239 ms |
30672 KB |
Output is correct |
25 |
Correct |
8 ms |
7704 KB |
Output is correct |
26 |
Correct |
2 ms |
6492 KB |
Output is correct |
27 |
Correct |
2 ms |
6488 KB |
Output is correct |
28 |
Correct |
12 ms |
8024 KB |
Output is correct |
29 |
Correct |
6 ms |
7260 KB |
Output is correct |
30 |
Correct |
2 ms |
6748 KB |
Output is correct |
31 |
Correct |
2 ms |
6748 KB |
Output is correct |
32 |
Correct |
2 ms |
6748 KB |
Output is correct |
33 |
Correct |
2 ms |
6748 KB |
Output is correct |
34 |
Correct |
6 ms |
7260 KB |
Output is correct |
35 |
Correct |
1 ms |
6492 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Correct |
1 ms |
6492 KB |
Output is correct |
38 |
Correct |
2 ms |
6492 KB |
Output is correct |
39 |
Correct |
1 ms |
6492 KB |
Output is correct |
40 |
Correct |
249 ms |
37052 KB |
Output is correct |
41 |
Correct |
263 ms |
30244 KB |
Output is correct |
42 |
Correct |
281 ms |
29760 KB |
Output is correct |
43 |
Correct |
66 ms |
18260 KB |
Output is correct |
44 |
Correct |
83 ms |
18432 KB |
Output is correct |
45 |
Correct |
223 ms |
26268 KB |
Output is correct |
46 |
Correct |
196 ms |
25968 KB |
Output is correct |
47 |
Correct |
307 ms |
38880 KB |
Output is correct |
48 |
Correct |
74 ms |
18520 KB |
Output is correct |
49 |
Correct |
211 ms |
37756 KB |
Output is correct |
50 |
Correct |
243 ms |
30760 KB |
Output is correct |
51 |
Correct |
207 ms |
26160 KB |
Output is correct |