# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244416 | 2020-07-04T03:08:05 Z | arnold518 | Price List (POI13_cen) | C++14 | 4000 ms | 19236 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; const int INF = 2e9; int N, M, K, A, B; pii E[MAXN+10]; vector<int> adj[MAXN/2+10], adj2[MAXN/2+10]; int dist[MAXN+10][2]; int ans[MAXN/2+10]; struct Queue { int v; ll w; int p; bool operator < (const Queue &p) const { return w>p.w; } }; bool f(int u, int v) { return binary_search(adj2[u].begin(), adj2[u].end(), v); } int main() { int i, j; scanf("%d%d%d%d%d", &N, &M, &K, &A, &B); for(i=1; i<=M; i++) { int u, v; scanf("%d%d", &u, &v); E[i*2-1]={u, v}; E[i*2]={v, u}; adj[u].push_back(i*2-1); adj[v].push_back(i*2); adj2[u].push_back(v); adj2[v].push_back(u); } for(i=1; i<=N; i++) sort(adj2[i].begin(), adj2[i].end()); for(i=1; i<=2*M; i++) dist[i][0]=dist[i][1]=INF; priority_queue<Queue> PQ; for(auto it : adj[K]) { PQ.push({it, 2*A, 0}); dist[it][0]=2*A; PQ.push({it, B, 1}); dist[it][1]=B; } while(!PQ.empty()) { Queue now=PQ.top(); PQ.pop(); if(dist[now.v][now.p]!=now.w) continue; if(now.p==1) { for(auto nxt : adj[E[now.v].second]) { if(f(E[now.v].first, E[nxt].second)) continue; if(dist[nxt][0]>now.w+B) PQ.push({nxt, now.w+B, 0}), dist[nxt][0]=now.w+B; } } else { for(auto nxt : adj[E[now.v].second]) { if(dist[nxt][0]>now.w+2*A) PQ.push({nxt, now.w+2*A, 0}), dist[nxt][0]=now.w+2*A; if(dist[nxt][1]>now.w+B) PQ.push({nxt, now.w+B, 1}), dist[nxt][1]=now.w+B; } } } for(i=1; i<=N; i++) if(i!=K) ans[i]=INF; for(i=1; i<=2*M; i++) ans[E[i].second]=min(ans[E[i].second], dist[i][0]); for(i=1; i<=N; i++) printf("%lld\n", ans[i]/2); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 7 ms | 5044 KB | Output is correct |
3 | Correct | 7 ms | 4992 KB | Output is correct |
4 | Correct | 7 ms | 4992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 5120 KB | Output is correct |
2 | Correct | 7 ms | 5120 KB | Output is correct |
3 | Correct | 7 ms | 5120 KB | Output is correct |
4 | Correct | 7 ms | 4992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 5120 KB | Output is correct |
2 | Correct | 8 ms | 5120 KB | Output is correct |
3 | Correct | 8 ms | 5120 KB | Output is correct |
4 | Correct | 8 ms | 5120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 6720 KB | Output is correct |
2 | Correct | 87 ms | 6848 KB | Output is correct |
3 | Correct | 30 ms | 6656 KB | Output is correct |
4 | Correct | 26 ms | 6656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2529 ms | 11128 KB | Output is correct |
2 | Execution timed out | 4086 ms | 11120 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3010 ms | 14956 KB | Output is correct |
2 | Correct | 1608 ms | 13296 KB | Output is correct |
3 | Correct | 170 ms | 14200 KB | Output is correct |
4 | Correct | 153 ms | 14328 KB | Output is correct |
5 | Execution timed out | 4078 ms | 16484 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4098 ms | 15856 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4100 ms | 17388 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1414 ms | 16752 KB | Output is correct |
2 | Correct | 1376 ms | 16952 KB | Output is correct |
3 | Correct | 200 ms | 15608 KB | Output is correct |
4 | Correct | 152 ms | 14456 KB | Output is correct |
5 | Execution timed out | 4096 ms | 19236 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 132 ms | 15608 KB | Output is correct |
2 | Correct | 128 ms | 15608 KB | Output is correct |
3 | Correct | 213 ms | 15480 KB | Output is correct |
4 | Correct | 159 ms | 13304 KB | Output is correct |
5 | Execution timed out | 4100 ms | 19172 KB | Time limit exceeded |