# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
36207 | 2017-12-06T10:36:34 Z | WhipppedCream | Price List (POI13_cen) | C++14 | 113 ms | 11204 KB |
#include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vvi vector< vi > #define vii vector< ii > #define mp make_pair #define pb push_back const int maxn = 1e5+5; int n, m, k, a, b; vector<int> adj[maxn]; vector< ii > adj2[maxn]; int dist[maxn]; ll len[maxn]; ll cost(int x) { return 1LL*min(2*a, b)*(x/2)+a*(x%2); } int main() { //#ifndef atom //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); //#endif scanf("%d %d %d %d %d", &n, &m, &k, &a, &b); for(int i = 1; i<= n; i++) dist[i] = len[i] = 1e9; for(int i = 1; i<= m; i++) { int a, b; scanf("%d %d", &a, &b); adj[a].pb(b); adj[b].pb(a); } dist[k] = 0; queue<int> Q; Q.push(k); while(!Q.empty()) { int u = Q.front(); Q.pop(); for(auto v : adj[u]) { if(dist[v]>dist[u]+1) { dist[v] = dist[u]+1; Q.push(v); } } } for(int i = 1; i<= n; i++) len[i] = cost(dist[i]); for(int i = 1; i<= n; i++) { for(auto v : adj[i]) { if(v == k) continue; if(dist[i]%2 == dist[v]%2) { len[i] = min(1LL*len[i], cost(dist[v]+1)); len[v] = min(1LL*len[v], cost(dist[i]+1)); } } } for(int i = 1; i<= n; i++) printf("%lld\n", len[i]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 7880 KB | Output is correct |
2 | Correct | 3 ms | 7880 KB | Output is correct |
3 | Incorrect | 0 ms | 7880 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7880 KB | Output is correct |
2 | Correct | 0 ms | 7880 KB | Output is correct |
3 | Incorrect | 0 ms | 7880 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7880 KB | Output is correct |
2 | Correct | 3 ms | 7880 KB | Output is correct |
3 | Incorrect | 0 ms | 7880 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8280 KB | Output is correct |
2 | Correct | 6 ms | 8280 KB | Output is correct |
3 | Incorrect | 16 ms | 8276 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 29 ms | 9332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 10296 KB | Output is correct |
2 | Correct | 63 ms | 9900 KB | Output is correct |
3 | Incorrect | 113 ms | 10124 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 83 ms | 10844 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 83 ms | 11204 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 86 ms | 10932 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 11048 KB | Output is correct |
2 | Correct | 106 ms | 10916 KB | Output is correct |
3 | Incorrect | 113 ms | 11048 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |