#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 1e5 + 5;
int n, m;
void dijkstra(vector <pii> *adj, ll *dist, int s) {
rep(i, 1, n) dist[i] = INF;
priority_queue <pii, vector <pii>, greater <pii>> q;
q.push({0, s});
dist[s] = 0;
while (q.size()) {
ll w = q.top().st, u = q.top().nd; q.pop();
if (w > dist[u]) continue;
for (pii x: adj[u]) {
int v = x.st, cost = x.nd;
ll newCost = w + cost;
if (newCost < dist[v]) {
dist[v] = newCost;
q.push({dist[v], v});
}
}
}
}
int U, V, S, T;
ll f[N], p[N];
vector <pii> d[N];
void initGraph() {
rep(i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
d[u].push_back({v, w});
d[v].push_back({u, w});
}
dijkstra(d, f, S);
dijkstra(d, p, T);
}
namespace sub12 {
vector <pii> g[N];
ll ans[N];
void solve() {
ll mi = f[T];
rep(i, 1, n) {
g[i] = d[i];
for (pii &x: g[i]) {
ll w = x.nd, j = x.st;
if (f[i] + w + p[j] == mi || f[j] + w + p[i] == mi)
x.nd = 0;
}
}
dijkstra(g, ans, U);
cout << ans[V];
}
}
namespace sub3 {
ll fu[N], fv[N], mi, ans;
bool vis[N];
void dfs(int r, int u) {
vis[u] = true;
ans = min(ans, min(fu[r] + fv[u], fv[r] + fu[u]));
for (pii x: d[u])
if (f[u] + x.nd + p[x.st] == mi && !vis[x.st])
dfs(r, x.st);
}
void solve() {
mi = f[T];
dijkstra(d, fu, U);
dijkstra(d, fv, V);
ans = fu[V];
rep(i, 1, n) if (f[i] + p[i] == mi) {
rep(j, 1, n) vis[j] = false;
dfs(i, i);
}
cout << ans << '\n';
}
}
namespace sub4 {
// dp on dag
// dp[i] = shortest path from some node to V
ll fu[N], fv[N], mi, ans, dpv[N], dpu[N];
bool vis[N];
void dfs(int u) {
vis[u] = true;
dpv[u] = fv[u];
dpu[u] = fu[u];
for (pii x: d[u]) {
int v = x.st, w = x.nd;
if (f[u] + w + p[v] == mi) {
if (!vis[v]) dfs(v);
dpv[u] = min(dpv[u], dpv[v]);
dpu[u] = min(dpu[u], dpu[v]);
}
}
}
void solve() {
mi = f[T];
dijkstra(d, fu, U);
dijkstra(d, fv, V);
rep(i, 1, n) dpv[i] = dpu[i] = INF;
dfs(S);
ans = fu[V];
rep(i, 1, n) ans = min(ans, min(fv[i] + dpu[i], fu[i] + dpv[i]));
cout << ans << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> S >> T >> U >> V;
initGraph();
// if (n <= 500)
// sub3 :: solve();
// else
// sub12 :: solve();
sub4 :: solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
295 ms |
25468 KB |
Output is correct |
2 |
Correct |
264 ms |
23956 KB |
Output is correct |
3 |
Correct |
325 ms |
29708 KB |
Output is correct |
4 |
Correct |
278 ms |
25408 KB |
Output is correct |
5 |
Correct |
286 ms |
23768 KB |
Output is correct |
6 |
Correct |
291 ms |
25700 KB |
Output is correct |
7 |
Correct |
278 ms |
23776 KB |
Output is correct |
8 |
Correct |
289 ms |
23812 KB |
Output is correct |
9 |
Correct |
259 ms |
24732 KB |
Output is correct |
10 |
Correct |
227 ms |
24672 KB |
Output is correct |
11 |
Correct |
111 ms |
19628 KB |
Output is correct |
12 |
Correct |
303 ms |
24692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
327 ms |
25668 KB |
Output is correct |
2 |
Correct |
335 ms |
26000 KB |
Output is correct |
3 |
Correct |
295 ms |
25424 KB |
Output is correct |
4 |
Correct |
304 ms |
25796 KB |
Output is correct |
5 |
Correct |
291 ms |
26068 KB |
Output is correct |
6 |
Correct |
262 ms |
27688 KB |
Output is correct |
7 |
Correct |
312 ms |
28004 KB |
Output is correct |
8 |
Correct |
287 ms |
25748 KB |
Output is correct |
9 |
Correct |
281 ms |
26152 KB |
Output is correct |
10 |
Correct |
297 ms |
25520 KB |
Output is correct |
11 |
Correct |
136 ms |
20984 KB |
Output is correct |
12 |
Correct |
274 ms |
28016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
6824 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5032 KB |
Output is correct |
4 |
Correct |
15 ms |
8576 KB |
Output is correct |
5 |
Correct |
10 ms |
6712 KB |
Output is correct |
6 |
Correct |
4 ms |
5168 KB |
Output is correct |
7 |
Correct |
5 ms |
5228 KB |
Output is correct |
8 |
Correct |
5 ms |
5300 KB |
Output is correct |
9 |
Correct |
4 ms |
5204 KB |
Output is correct |
10 |
Correct |
11 ms |
6740 KB |
Output is correct |
11 |
Correct |
3 ms |
5040 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
295 ms |
25468 KB |
Output is correct |
2 |
Correct |
264 ms |
23956 KB |
Output is correct |
3 |
Correct |
325 ms |
29708 KB |
Output is correct |
4 |
Correct |
278 ms |
25408 KB |
Output is correct |
5 |
Correct |
286 ms |
23768 KB |
Output is correct |
6 |
Correct |
291 ms |
25700 KB |
Output is correct |
7 |
Correct |
278 ms |
23776 KB |
Output is correct |
8 |
Correct |
289 ms |
23812 KB |
Output is correct |
9 |
Correct |
259 ms |
24732 KB |
Output is correct |
10 |
Correct |
227 ms |
24672 KB |
Output is correct |
11 |
Correct |
111 ms |
19628 KB |
Output is correct |
12 |
Correct |
303 ms |
24692 KB |
Output is correct |
13 |
Correct |
327 ms |
25668 KB |
Output is correct |
14 |
Correct |
335 ms |
26000 KB |
Output is correct |
15 |
Correct |
295 ms |
25424 KB |
Output is correct |
16 |
Correct |
304 ms |
25796 KB |
Output is correct |
17 |
Correct |
291 ms |
26068 KB |
Output is correct |
18 |
Correct |
262 ms |
27688 KB |
Output is correct |
19 |
Correct |
312 ms |
28004 KB |
Output is correct |
20 |
Correct |
287 ms |
25748 KB |
Output is correct |
21 |
Correct |
281 ms |
26152 KB |
Output is correct |
22 |
Correct |
297 ms |
25520 KB |
Output is correct |
23 |
Correct |
136 ms |
20984 KB |
Output is correct |
24 |
Correct |
274 ms |
28016 KB |
Output is correct |
25 |
Correct |
10 ms |
6824 KB |
Output is correct |
26 |
Correct |
4 ms |
5120 KB |
Output is correct |
27 |
Correct |
4 ms |
5032 KB |
Output is correct |
28 |
Correct |
15 ms |
8576 KB |
Output is correct |
29 |
Correct |
10 ms |
6712 KB |
Output is correct |
30 |
Correct |
4 ms |
5168 KB |
Output is correct |
31 |
Correct |
5 ms |
5228 KB |
Output is correct |
32 |
Correct |
5 ms |
5300 KB |
Output is correct |
33 |
Correct |
4 ms |
5204 KB |
Output is correct |
34 |
Correct |
11 ms |
6740 KB |
Output is correct |
35 |
Correct |
3 ms |
5040 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
3 ms |
5076 KB |
Output is correct |
38 |
Correct |
3 ms |
5076 KB |
Output is correct |
39 |
Correct |
3 ms |
5076 KB |
Output is correct |
40 |
Correct |
245 ms |
25496 KB |
Output is correct |
41 |
Correct |
274 ms |
24616 KB |
Output is correct |
42 |
Correct |
268 ms |
24892 KB |
Output is correct |
43 |
Correct |
156 ms |
20300 KB |
Output is correct |
44 |
Correct |
119 ms |
20232 KB |
Output is correct |
45 |
Correct |
313 ms |
24480 KB |
Output is correct |
46 |
Correct |
296 ms |
23488 KB |
Output is correct |
47 |
Correct |
261 ms |
25348 KB |
Output is correct |
48 |
Correct |
109 ms |
17684 KB |
Output is correct |
49 |
Correct |
285 ms |
25040 KB |
Output is correct |
50 |
Correct |
289 ms |
23836 KB |
Output is correct |
51 |
Correct |
302 ms |
23832 KB |
Output is correct |