# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42113 | 2018-02-22T16:36:53 Z | nonocut | Commuter Pass (JOI18_commuter_pass) | C++14 | 2000 ms | 262144 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define X first #define Y second const int maxn = 100005; const ll inf = 1e18; struct node { int x; ll val; node(int _x = 0, ll _val = 0) { x = _x; val = _val; }; bool operator < (node a) const { return a.val<val; } }; int n,m,a,b,c,d; bool vis[maxn]; ll dist[maxn], da[maxn], db[maxn], dc[maxn], dd[maxn]; vector<pair<int,ll>> way[maxn]; priority_queue<node> heap; vector<int> from[maxn]; vector<int> topo; ll mn[maxn]; ll ans; void sssp(int u) { for(int i=1;i<=n;i++) dist[i] = inf, vis[i] = 0; dist[u] = 0; heap.push(node(u,0)); while(!heap.empty()) { int u = heap.top().x; heap.pop(); if(vis[u]) continue; vis[u] = 1; for(auto t : way[u]) { if(dist[t.X] > dist[u] + t.Y) { dist[t.X] = dist[u] + t.Y; heap.push(node(t.X,dist[t.X])); } } } } void tsort(int u) { for(auto v : from[u]) tsort(v); topo.push_back(u); } void solve() { for(int x=1;x<=n;x++) mn[x] = dc[x]; for(auto u : topo) { ans = min(ans, mn[u] + dd[u]); for(auto v : from[u]) { mn[v] = min(mn[v], mn[u]); } } } int main() { scanf("%d%d",&n,&m); scanf("%d%d%d%d",&a,&b,&c,&d); for(int i=0;i<m;i++) { int x,y; ll val; scanf("%d%d%lld",&x,&y,&val); way[x].pb({y,val}); way[y].pb({x,val}); } sssp(a); for(int i=1;i<=n;i++) da[i] = dist[i]; sssp(b); for(int i=1;i<=n;i++) db[i] = dist[i]; sssp(c); for(int i=1;i<=n;i++) dc[i] = dist[i]; sssp(d); for(int i=1;i<=n;i++) dd[i] = dist[i]; for(int x=1;x<=n;x++) { for(auto t : way[x]) { if(da[x]+db[t.X]+t.Y==da[b]) from[x].pb(t.X); } } tsort(a); reverse(topo.begin(),topo.end()); ans = dc[d]; solve(); swap(dc,dd); solve(); printf("%lld",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 457 ms | 21404 KB | Output is correct |
2 | Execution timed out | 2072 ms | 262144 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 501 ms | 262144 KB | Output is correct |
2 | Correct | 482 ms | 262144 KB | Output is correct |
3 | Correct | 503 ms | 262144 KB | Output is correct |
4 | Correct | 509 ms | 262144 KB | Output is correct |
5 | Correct | 524 ms | 262144 KB | Output is correct |
6 | Correct | 549 ms | 262144 KB | Output is correct |
7 | Correct | 585 ms | 262144 KB | Output is correct |
8 | Correct | 530 ms | 262144 KB | Output is correct |
9 | Correct | 552 ms | 262144 KB | Output is correct |
10 | Correct | 562 ms | 262144 KB | Output is correct |
11 | Correct | 266 ms | 262144 KB | Output is correct |
12 | Correct | 520 ms | 262144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1110 ms | 262144 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 457 ms | 21404 KB | Output is correct |
2 | Execution timed out | 2072 ms | 262144 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |