#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const ll inf = 1e18;
int nodes, edges;
vector<pair<int, ll>> adj[MAXN];
void dijkstra(int source, vector<ll> &dist){
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, source});
for (int i = 1; i <= nodes; i++) dist[i] = inf;
dist[source] = 0;
while (!pq.empty()){
ll d = pq.top().first; int x = pq.top().second; pq.pop();
if (dist[x] != d) continue;
for (auto nxt : adj[x]){
int nn = nxt.first; ll nd = nxt.second;
if (d + nd < dist[nn]){
dist[nn] = d + nd;
pq.push({dist[nn], nn});
}
}
}
}
ll dp(int x, vector<vector<int>> &spadj, vector<ll> &ddest, vector<ll> &memo){
if (memo[x] != -1) return memo[x];
ll ans = ddest[x];
for (int nxt : spadj[x]) ans = min(ans, dp(nxt, spadj, ddest, memo));
return memo[x] = ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int s, t, u, v; cin >> nodes >> edges >> s >> t >> u >> v;
vector<tuple<int, int, ll>> elist(edges);
for (int i = 0; i < edges; i++){
int a, b; ll d; cin >> a >> b >> d;
adj[a].push_back({b, d});
adj[b].push_back({a, d});
elist[i] = {a, b, d};
}
vector<ll> ds(nodes + 1), dt(nodes + 1), du(nodes + 1), dv(nodes + 1);
dijkstra(s, ds); dijkstra(t, dt); dijkstra(u, du); dijkstra(v, dv);
ll dst = ds[t];
vector<vector<int>> stot(nodes + 1), ttos(nodes + 1);
for (auto edge : elist){
int a, b; ll d; tie(a, b, d) = edge;
if (ds[a] + d + dt[b] == dst){
stot[a].push_back(b);
ttos[b].push_back(a);
}
else if (ds[b] + d + dt[a] == dst){
stot[b].push_back(a);
ttos[a].push_back(b);
}
}
vector<ll> memo1(nodes + 1, -1), memo2(nodes + 1, -1);
ll ans = du[v];
for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, stot, dv, memo1));
for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, ttos, dv, memo2));
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
29428 KB |
Output is correct |
2 |
Correct |
349 ms |
30324 KB |
Output is correct |
3 |
Correct |
359 ms |
35700 KB |
Output is correct |
4 |
Correct |
274 ms |
29332 KB |
Output is correct |
5 |
Correct |
348 ms |
31820 KB |
Output is correct |
6 |
Correct |
333 ms |
29320 KB |
Output is correct |
7 |
Correct |
324 ms |
32376 KB |
Output is correct |
8 |
Correct |
339 ms |
31908 KB |
Output is correct |
9 |
Correct |
296 ms |
30040 KB |
Output is correct |
10 |
Correct |
220 ms |
30004 KB |
Output is correct |
11 |
Correct |
156 ms |
26036 KB |
Output is correct |
12 |
Correct |
286 ms |
29732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
352 ms |
32344 KB |
Output is correct |
2 |
Correct |
334 ms |
32228 KB |
Output is correct |
3 |
Correct |
342 ms |
31888 KB |
Output is correct |
4 |
Correct |
332 ms |
32628 KB |
Output is correct |
5 |
Correct |
350 ms |
32592 KB |
Output is correct |
6 |
Correct |
358 ms |
36204 KB |
Output is correct |
7 |
Correct |
377 ms |
36428 KB |
Output is correct |
8 |
Correct |
338 ms |
31608 KB |
Output is correct |
9 |
Correct |
370 ms |
32596 KB |
Output is correct |
10 |
Correct |
338 ms |
31968 KB |
Output is correct |
11 |
Correct |
164 ms |
28884 KB |
Output is correct |
12 |
Correct |
318 ms |
35920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
4820 KB |
Output is correct |
2 |
Correct |
3 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2680 KB |
Output is correct |
4 |
Correct |
15 ms |
6828 KB |
Output is correct |
5 |
Correct |
9 ms |
4732 KB |
Output is correct |
6 |
Correct |
2 ms |
2820 KB |
Output is correct |
7 |
Correct |
3 ms |
2900 KB |
Output is correct |
8 |
Correct |
3 ms |
2900 KB |
Output is correct |
9 |
Correct |
3 ms |
2772 KB |
Output is correct |
10 |
Correct |
8 ms |
4692 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
29428 KB |
Output is correct |
2 |
Correct |
349 ms |
30324 KB |
Output is correct |
3 |
Correct |
359 ms |
35700 KB |
Output is correct |
4 |
Correct |
274 ms |
29332 KB |
Output is correct |
5 |
Correct |
348 ms |
31820 KB |
Output is correct |
6 |
Correct |
333 ms |
29320 KB |
Output is correct |
7 |
Correct |
324 ms |
32376 KB |
Output is correct |
8 |
Correct |
339 ms |
31908 KB |
Output is correct |
9 |
Correct |
296 ms |
30040 KB |
Output is correct |
10 |
Correct |
220 ms |
30004 KB |
Output is correct |
11 |
Correct |
156 ms |
26036 KB |
Output is correct |
12 |
Correct |
286 ms |
29732 KB |
Output is correct |
13 |
Correct |
352 ms |
32344 KB |
Output is correct |
14 |
Correct |
334 ms |
32228 KB |
Output is correct |
15 |
Correct |
342 ms |
31888 KB |
Output is correct |
16 |
Correct |
332 ms |
32628 KB |
Output is correct |
17 |
Correct |
350 ms |
32592 KB |
Output is correct |
18 |
Correct |
358 ms |
36204 KB |
Output is correct |
19 |
Correct |
377 ms |
36428 KB |
Output is correct |
20 |
Correct |
338 ms |
31608 KB |
Output is correct |
21 |
Correct |
370 ms |
32596 KB |
Output is correct |
22 |
Correct |
338 ms |
31968 KB |
Output is correct |
23 |
Correct |
164 ms |
28884 KB |
Output is correct |
24 |
Correct |
318 ms |
35920 KB |
Output is correct |
25 |
Correct |
10 ms |
4820 KB |
Output is correct |
26 |
Correct |
3 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2680 KB |
Output is correct |
28 |
Correct |
15 ms |
6828 KB |
Output is correct |
29 |
Correct |
9 ms |
4732 KB |
Output is correct |
30 |
Correct |
2 ms |
2820 KB |
Output is correct |
31 |
Correct |
3 ms |
2900 KB |
Output is correct |
32 |
Correct |
3 ms |
2900 KB |
Output is correct |
33 |
Correct |
3 ms |
2772 KB |
Output is correct |
34 |
Correct |
8 ms |
4692 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
2 ms |
2644 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
3 ms |
2772 KB |
Output is correct |
39 |
Correct |
2 ms |
2772 KB |
Output is correct |
40 |
Correct |
276 ms |
28820 KB |
Output is correct |
41 |
Correct |
296 ms |
29756 KB |
Output is correct |
42 |
Correct |
294 ms |
29816 KB |
Output is correct |
43 |
Correct |
198 ms |
30380 KB |
Output is correct |
44 |
Correct |
195 ms |
30576 KB |
Output is correct |
45 |
Correct |
384 ms |
34608 KB |
Output is correct |
46 |
Correct |
369 ms |
34476 KB |
Output is correct |
47 |
Correct |
295 ms |
29284 KB |
Output is correct |
48 |
Correct |
157 ms |
27616 KB |
Output is correct |
49 |
Correct |
227 ms |
28456 KB |
Output is correct |
50 |
Correct |
356 ms |
33400 KB |
Output is correct |
51 |
Correct |
380 ms |
34716 KB |
Output is correct |