# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
36519 | 2017-12-10T06:30:19 Z | WhipppedCream | Price List (POI13_cen) | C++14 | 336 ms | 28948 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]; set<int> has[maxn]; vector<int> active[maxn]; bool vis[maxn]; int dist[maxn]; int dist2[maxn]; void bfs(int *dist) { for(int i = 1; i<= n; i++) dist[i] = 1e9; 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); } } } } void bfs2(int *dist) { for(int i = 1; i<= n; i++) dist[i] = 1e9; queue<int> Q; Q.push(k); dist[k] = 0; vis[k] = 1; for(int i = 1; i<= n; i++) active[i] = adj[i]; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(auto v : adj[u]) { vector<int> temp; for(auto w : active[v]) { if(vis[w]) continue; temp.pb(w); if(has[u].find(w) != has[u].end()) continue; vis[w] = 1; dist[w] = dist[u]+1; Q.push(w); } active[v] = temp; } } } 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<= m; i++) { int a, b; scanf("%d %d", &a, &b); adj[a].pb(b); adj[b].pb(a); has[a].insert(b); has[b].insert(a); } bfs(dist); bfs2(dist2); //for(int i = 1; i<= n; i++) printf("%d\n", dist2[i]); for(int i = 1; i<= n; i++) { int x = (dist[i]/2)*min(2*a, b)+(dist[i]%2)*a; if(dist2[i] != 1e9) x= min(x, dist2[i]*b); printf("%d\n", x); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 12276 KB | Output is correct |
2 | Correct | 6 ms | 12276 KB | Output is correct |
3 | Correct | 0 ms | 12276 KB | Output is correct |
4 | Correct | 0 ms | 12276 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 12276 KB | Output is correct |
2 | Correct | 3 ms | 12276 KB | Output is correct |
3 | Correct | 0 ms | 12276 KB | Output is correct |
4 | Correct | 6 ms | 12276 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 12408 KB | Output is correct |
2 | Correct | 0 ms | 12408 KB | Output is correct |
3 | Correct | 3 ms | 12408 KB | Output is correct |
4 | Correct | 3 ms | 12408 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 14256 KB | Output is correct |
2 | Correct | 19 ms | 14256 KB | Output is correct |
3 | Correct | 29 ms | 14652 KB | Output is correct |
4 | Correct | 23 ms | 14652 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 86 ms | 19096 KB | Output is correct |
2 | Correct | 99 ms | 18984 KB | Output is correct |
3 | Correct | 99 ms | 17952 KB | Output is correct |
4 | Correct | 146 ms | 20064 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 196 ms | 23776 KB | Output is correct |
2 | Correct | 183 ms | 22216 KB | Output is correct |
3 | Correct | 269 ms | 25212 KB | Output is correct |
4 | Correct | 296 ms | 25740 KB | Output is correct |
5 | Correct | 179 ms | 24952 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 239 ms | 26064 KB | Output is correct |
2 | Correct | 173 ms | 22572 KB | Output is correct |
3 | Correct | 293 ms | 26136 KB | Output is correct |
4 | Correct | 313 ms | 25740 KB | Output is correct |
5 | Correct | 243 ms | 26548 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 286 ms | 28320 KB | Output is correct |
2 | Correct | 299 ms | 26532 KB | Output is correct |
3 | Correct | 336 ms | 26796 KB | Output is correct |
4 | Correct | 309 ms | 25740 KB | Output is correct |
5 | Correct | 266 ms | 27836 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 316 ms | 27200 KB | Output is correct |
2 | Correct | 293 ms | 27260 KB | Output is correct |
3 | Correct | 306 ms | 26928 KB | Output is correct |
4 | Correct | 319 ms | 25740 KB | Output is correct |
5 | Correct | 266 ms | 28936 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 283 ms | 27852 KB | Output is correct |
2 | Correct | 249 ms | 27720 KB | Output is correct |
3 | Correct | 336 ms | 27984 KB | Output is correct |
4 | Correct | 279 ms | 25740 KB | Output is correct |
5 | Correct | 283 ms | 28948 KB | Output is correct |