#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pl;
typedef tuple<int,int,int> tt;
#define all(v) v.begin(), v.end()
const int mn = 1e5 + 10;
ll dist[4][mn], dp[mn];
vector<pl> adj[mn], subg[mn];
bool vis[mn];
int n, node;
void dijkstra (int save, int source) {
for (int i = 1; i <= n; i++) vis[i] = 0, dist[save][i] = LLONG_MAX;
dist[save][source] = 0;
priority_queue<pl> pq;
pq.push({0, source});
while (pq.size()) {
int a = pq.top().second; pq.pop();
if (vis[a]) continue;
vis[a] = 1;
for (pl it : adj[a]) {
ll w; int b; tie(w, b) = it;
if (dist[save][a] + w < dist[save][b]) {
dist[save][b] = dist[save][a] + w;
pq.push({-dist[save][b], b});
}
}
}
return;
}
void addEdge (int a, int b, ll c) {
subg[a].push_back({c, b});
}
ll finalD() {
for (int i = 0; i <= node; i++) vis[i] = 0, dp[i] = LLONG_MAX;
dp[0] = 0;
priority_queue<pl> pq;
pq.push({0, 0});
while (pq.size()) {
int a = pq.top().second; pq.pop();
if (vis[a]) continue;
vis[a] = 1;
for (pl it : subg[a]) {
ll w; int b; tie(w, b) = it;
if (dp[a] + w < dp[b]) {
dp[b] = dp[a] + w;
pq.push({-dp[b], b});
}
}
}
return dp[node];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m; cin >> n >> m;
int s, t, u, v; cin >> s >> t >> u >> v;
node = n + 1;
vector<tt> edge(m);
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({c, b});
adj[b].push_back({c, a});
edge[i] = make_tuple(a, b, c);
}
dijkstra(0, s);
dijkstra(1, t);
dijkstra(2, u);
dijkstra(3, v);
ll ans = dist[2][v];
for (int i = 1; i <= n; i++) {
if (dist[0][i] + dist[1][i] > dist[0][t]) continue;
addEdge(0, i, dist[2][i]);
addEdge(i, node, dist[3][i]);
}
for (int i = 0; i < m; i++) {
int a, b; ll c; tie(a, b, c) = edge[i];
if (dist[0][a] + c + dist[1][b] == dist[0][t]) addEdge(a, b, 0);
if (dist[0][b] + c + dist[1][a] == dist[0][t]) addEdge(b, a, 0);
}
ans = min(ans, finalD());
for (int i = 0; i <= node; i++) subg[i].clear();
for (int i = 1; i <= n; i++) {
if (dist[0][i] + dist[1][i] > dist[0][t]) continue;
addEdge(0, i, dist[2][i]);
addEdge(i, node, dist[3][i]);
}
for (int i = 0; i < m; i++) {
int a, b; ll c; tie(a, b, c) = edge[i];
if (dist[0][a] + c + dist[1][b] == dist[0][t]) addEdge(b, a, 0);
if (dist[0][b] + c + dist[1][a] == dist[0][t]) addEdge(a, b, 0);
}
ans = min(ans, finalD());
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
193 ms |
25256 KB |
Output is correct |
2 |
Correct |
285 ms |
24584 KB |
Output is correct |
3 |
Correct |
239 ms |
29040 KB |
Output is correct |
4 |
Correct |
177 ms |
24692 KB |
Output is correct |
5 |
Correct |
250 ms |
27824 KB |
Output is correct |
6 |
Correct |
201 ms |
25232 KB |
Output is correct |
7 |
Correct |
243 ms |
28052 KB |
Output is correct |
8 |
Correct |
244 ms |
27320 KB |
Output is correct |
9 |
Correct |
192 ms |
23812 KB |
Output is correct |
10 |
Correct |
157 ms |
23348 KB |
Output is correct |
11 |
Correct |
84 ms |
20148 KB |
Output is correct |
12 |
Correct |
190 ms |
23656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
264 ms |
24700 KB |
Output is correct |
2 |
Correct |
218 ms |
25044 KB |
Output is correct |
3 |
Correct |
246 ms |
23872 KB |
Output is correct |
4 |
Correct |
214 ms |
24884 KB |
Output is correct |
5 |
Correct |
222 ms |
25644 KB |
Output is correct |
6 |
Correct |
310 ms |
27624 KB |
Output is correct |
7 |
Correct |
248 ms |
28996 KB |
Output is correct |
8 |
Correct |
223 ms |
25044 KB |
Output is correct |
9 |
Correct |
283 ms |
25284 KB |
Output is correct |
10 |
Correct |
220 ms |
23972 KB |
Output is correct |
11 |
Correct |
118 ms |
21880 KB |
Output is correct |
12 |
Correct |
222 ms |
27680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
8792 KB |
Output is correct |
3 |
Correct |
2 ms |
8796 KB |
Output is correct |
4 |
Correct |
15 ms |
11868 KB |
Output is correct |
5 |
Correct |
7 ms |
10332 KB |
Output is correct |
6 |
Correct |
3 ms |
8796 KB |
Output is correct |
7 |
Correct |
3 ms |
8796 KB |
Output is correct |
8 |
Correct |
3 ms |
8792 KB |
Output is correct |
9 |
Correct |
2 ms |
8796 KB |
Output is correct |
10 |
Correct |
7 ms |
10332 KB |
Output is correct |
11 |
Correct |
2 ms |
8540 KB |
Output is correct |
12 |
Correct |
2 ms |
8536 KB |
Output is correct |
13 |
Correct |
2 ms |
8540 KB |
Output is correct |
14 |
Correct |
2 ms |
8796 KB |
Output is correct |
15 |
Correct |
2 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
193 ms |
25256 KB |
Output is correct |
2 |
Correct |
285 ms |
24584 KB |
Output is correct |
3 |
Correct |
239 ms |
29040 KB |
Output is correct |
4 |
Correct |
177 ms |
24692 KB |
Output is correct |
5 |
Correct |
250 ms |
27824 KB |
Output is correct |
6 |
Correct |
201 ms |
25232 KB |
Output is correct |
7 |
Correct |
243 ms |
28052 KB |
Output is correct |
8 |
Correct |
244 ms |
27320 KB |
Output is correct |
9 |
Correct |
192 ms |
23812 KB |
Output is correct |
10 |
Correct |
157 ms |
23348 KB |
Output is correct |
11 |
Correct |
84 ms |
20148 KB |
Output is correct |
12 |
Correct |
190 ms |
23656 KB |
Output is correct |
13 |
Correct |
264 ms |
24700 KB |
Output is correct |
14 |
Correct |
218 ms |
25044 KB |
Output is correct |
15 |
Correct |
246 ms |
23872 KB |
Output is correct |
16 |
Correct |
214 ms |
24884 KB |
Output is correct |
17 |
Correct |
222 ms |
25644 KB |
Output is correct |
18 |
Correct |
310 ms |
27624 KB |
Output is correct |
19 |
Correct |
248 ms |
28996 KB |
Output is correct |
20 |
Correct |
223 ms |
25044 KB |
Output is correct |
21 |
Correct |
283 ms |
25284 KB |
Output is correct |
22 |
Correct |
220 ms |
23972 KB |
Output is correct |
23 |
Correct |
118 ms |
21880 KB |
Output is correct |
24 |
Correct |
222 ms |
27680 KB |
Output is correct |
25 |
Correct |
7 ms |
10588 KB |
Output is correct |
26 |
Correct |
2 ms |
8792 KB |
Output is correct |
27 |
Correct |
2 ms |
8796 KB |
Output is correct |
28 |
Correct |
15 ms |
11868 KB |
Output is correct |
29 |
Correct |
7 ms |
10332 KB |
Output is correct |
30 |
Correct |
3 ms |
8796 KB |
Output is correct |
31 |
Correct |
3 ms |
8796 KB |
Output is correct |
32 |
Correct |
3 ms |
8792 KB |
Output is correct |
33 |
Correct |
2 ms |
8796 KB |
Output is correct |
34 |
Correct |
7 ms |
10332 KB |
Output is correct |
35 |
Correct |
2 ms |
8540 KB |
Output is correct |
36 |
Correct |
2 ms |
8536 KB |
Output is correct |
37 |
Correct |
2 ms |
8540 KB |
Output is correct |
38 |
Correct |
2 ms |
8796 KB |
Output is correct |
39 |
Correct |
2 ms |
8796 KB |
Output is correct |
40 |
Correct |
177 ms |
24408 KB |
Output is correct |
41 |
Correct |
213 ms |
23700 KB |
Output is correct |
42 |
Correct |
195 ms |
23660 KB |
Output is correct |
43 |
Correct |
123 ms |
26344 KB |
Output is correct |
44 |
Correct |
142 ms |
26828 KB |
Output is correct |
45 |
Correct |
285 ms |
36444 KB |
Output is correct |
46 |
Correct |
273 ms |
36304 KB |
Output is correct |
47 |
Correct |
182 ms |
24828 KB |
Output is correct |
48 |
Correct |
126 ms |
26116 KB |
Output is correct |
49 |
Correct |
157 ms |
24556 KB |
Output is correct |
50 |
Correct |
240 ms |
33376 KB |
Output is correct |
51 |
Correct |
256 ms |
36516 KB |
Output is correct |