# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
60574 | 2018-07-24T11:07:10 Z | gusfring | Commuter Pass (JOI18_commuter_pass) | C++14 | 806 ms | 19596 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; typedef long long ll; struct node{ int u; ll w; bool operator<(const node &rhs) const{ return w > rhs.w; } }; vector<node> adj[MAXN]; int N, M, S, U, T, V; ll dists[MAXN], distt[MAXN], distu[MAXN], distv[MAXN]; void dijkstra(int cur, ll *dist){ for(int i=1; i<=N; ++i) dist[i] = -1; dist[cur] = 0; priority_queue<node> Q; Q.push((node){cur, 0}); while(!Q.empty()){ node it = Q.top(); Q.pop(); int u = it.u; ll w = it.w; for(node it2 : adj[u]){ int v = it2.u; ll ww = it2.w; if(dist[v] == -1 || dist[u] + ww < dist[v]){ dist[v] = dist[u] + ww; Q.push((node){v, dist[v]}); } } } } int main(){ scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V); while(M--){ int u, v, c; scanf("%d %d %d", &u, &v, &c); adj[u].push_back((node){v, c}); adj[v].push_back((node){u, c}); } dijkstra(S, dists); dijkstra(T, distt); dijkstra(U, distu); dijkstra(V, distv); ll mnu = 1000000000000000000LL, mnv = 1000000000000000000LL, ds = dists[T]; for(int i=1; i<=N; ++i) if(dists[i] + distt[i] == ds) mnu = min(mnu, distu[i]), mnv = min(mnv, distv[i]); printf("%lld\n", min(mnu + mnv, distu[V])); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 651 ms | 19444 KB | Output is correct |
2 | Correct | 716 ms | 19444 KB | Output is correct |
3 | Correct | 657 ms | 19444 KB | Output is correct |
4 | Correct | 557 ms | 19592 KB | Output is correct |
5 | Correct | 555 ms | 19592 KB | Output is correct |
6 | Correct | 625 ms | 19596 KB | Output is correct |
7 | Correct | 751 ms | 19596 KB | Output is correct |
8 | Correct | 596 ms | 19596 KB | Output is correct |
9 | Correct | 536 ms | 19596 KB | Output is correct |
10 | Correct | 449 ms | 19596 KB | Output is correct |
11 | Correct | 292 ms | 19596 KB | Output is correct |
12 | Correct | 762 ms | 19596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 719 ms | 19596 KB | Output is correct |
2 | Correct | 806 ms | 19596 KB | Output is correct |
3 | Correct | 742 ms | 19596 KB | Output is correct |
4 | Correct | 729 ms | 19596 KB | Output is correct |
5 | Correct | 700 ms | 19596 KB | Output is correct |
6 | Correct | 626 ms | 19596 KB | Output is correct |
7 | Correct | 788 ms | 19596 KB | Output is correct |
8 | Correct | 802 ms | 19596 KB | Output is correct |
9 | Correct | 705 ms | 19596 KB | Output is correct |
10 | Correct | 656 ms | 19596 KB | Output is correct |
11 | Correct | 252 ms | 19596 KB | Output is correct |
12 | Correct | 622 ms | 19596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 19596 KB | Output is correct |
2 | Correct | 5 ms | 19596 KB | Output is correct |
3 | Incorrect | 5 ms | 19596 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 651 ms | 19444 KB | Output is correct |
2 | Correct | 716 ms | 19444 KB | Output is correct |
3 | Correct | 657 ms | 19444 KB | Output is correct |
4 | Correct | 557 ms | 19592 KB | Output is correct |
5 | Correct | 555 ms | 19592 KB | Output is correct |
6 | Correct | 625 ms | 19596 KB | Output is correct |
7 | Correct | 751 ms | 19596 KB | Output is correct |
8 | Correct | 596 ms | 19596 KB | Output is correct |
9 | Correct | 536 ms | 19596 KB | Output is correct |
10 | Correct | 449 ms | 19596 KB | Output is correct |
11 | Correct | 292 ms | 19596 KB | Output is correct |
12 | Correct | 762 ms | 19596 KB | Output is correct |
13 | Correct | 719 ms | 19596 KB | Output is correct |
14 | Correct | 806 ms | 19596 KB | Output is correct |
15 | Correct | 742 ms | 19596 KB | Output is correct |
16 | Correct | 729 ms | 19596 KB | Output is correct |
17 | Correct | 700 ms | 19596 KB | Output is correct |
18 | Correct | 626 ms | 19596 KB | Output is correct |
19 | Correct | 788 ms | 19596 KB | Output is correct |
20 | Correct | 802 ms | 19596 KB | Output is correct |
21 | Correct | 705 ms | 19596 KB | Output is correct |
22 | Correct | 656 ms | 19596 KB | Output is correct |
23 | Correct | 252 ms | 19596 KB | Output is correct |
24 | Correct | 622 ms | 19596 KB | Output is correct |
25 | Correct | 22 ms | 19596 KB | Output is correct |
26 | Correct | 5 ms | 19596 KB | Output is correct |
27 | Incorrect | 5 ms | 19596 KB | Output isn't correct |
28 | Halted | 0 ms | 0 KB | - |