# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
60427 | 2018-07-24T07:35:43 Z | gusfring | Commuter Pass (JOI18_commuter_pass) | C++14 | 210 ms | 11128 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(min({dists[i], distt[i], distu[i], distv[i]}) == -1) continue; if(dists[i] + distt[i] == ds) mnu = min(mnu, distu[i]), mnv = min(mnv, distv[i]); } printf("%lld\n", mnu + mnv); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 196 ms | 11128 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 210 ms | 11128 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 22 ms | 11128 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 196 ms | 11128 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |