# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
84252 | 2018-11-14T03:10:38 Z | ToMoClone | Cities (BOI16_cities) | C++14 | 5466 ms | 137028 KB |
/*input 4 3 6 1 3 4 1 2 4 1 3 9 1 4 6 2 3 2 2 4 5 3 4 8 */ #pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; struct State { int node; int64_t d; int mask; State(int _node = 0, int64_t _d = 1e15, int _mask = 0) : node(_node), d(_d), mask(_mask) {} bool operator<(const State &x) const { return d > x.d; } }; const int N = 100005; int n, k, m; int64_t d[N][32]; queue<State> q; vector<pair<int, int> > G[N]; int32_t main(){ memset(d, 127, sizeof d); scanf("%d%d%d", &n, &k, &m); for(int i = 0; i < k; ++ i) { int a; scanf("%d", &a); d[a][1 << i] = 0, q.push(State(a, 0, 1 << i)); } for(int i = 1; i <= m; ++ i) { int u, v, c; scanf("%d%d%d", &u, &v, &c); G[u].push_back(make_pair(c, v)); G[v].push_back(make_pair(c, u)); } while(!q.empty()) { auto cur = q.front(); q.pop(); if(d[cur.node][cur.mask] != cur.d) continue; for(int i = 0; i < k; ++ i) if((cur.mask & (1 << i)) == 0) for(auto u : G[cur.node]) { if(d[cur.node][(1 << i) | cur.mask] > cur.d + d[u.second][1 << i] + u.first) { d[cur.node][(1 << i) | cur.mask] = cur.d + d[u.second][1 << i] + u.first; q.push(State(cur.node, d[cur.node][(1 << i) | cur.mask], (1 << i) | cur.mask)); } if(d[u.second][(1 << i) | cur.mask] > cur.d + d[u.second][1 << i] + u.first) { d[u.second][(1 << i) | cur.mask] = cur.d + d[u.second][1 << i] + u.first; q.push(State(u.second, d[u.second][(1 << i) | cur.mask], (1 << i) | cur.mask)); } } for(auto u : G[cur.node]) if(d[u.second][cur.mask] > cur.d + u.first) { d[u.second][cur.mask] = cur.d + u.first; q.push(State(u.second, d[u.second][cur.mask], cur.mask)); } } int64_t Ans = 1e15; for(int i = 1; i <= n; ++ i) Ans = min(Ans, d[i][(1 << k) - 1]); cout << Ans << endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 27640 KB | Output is correct |
2 | Correct | 25 ms | 27780 KB | Output is correct |
3 | Correct | 25 ms | 27968 KB | Output is correct |
4 | Correct | 25 ms | 27968 KB | Output is correct |
5 | Correct | 25 ms | 27968 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 791 ms | 51024 KB | Output is correct |
2 | Correct | 621 ms | 51024 KB | Output is correct |
3 | Correct | 172 ms | 51024 KB | Output is correct |
4 | Correct | 169 ms | 51024 KB | Output is correct |
5 | Correct | 384 ms | 51024 KB | Output is correct |
6 | Correct | 129 ms | 51024 KB | Output is correct |
7 | Correct | 27 ms | 51024 KB | Output is correct |
8 | Correct | 27 ms | 51024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 51024 KB | Output is correct |
2 | Correct | 30 ms | 51024 KB | Output is correct |
3 | Correct | 27 ms | 51024 KB | Output is correct |
4 | Correct | 29 ms | 51024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1972 ms | 76568 KB | Output is correct |
2 | Correct | 1715 ms | 77560 KB | Output is correct |
3 | Correct | 378 ms | 77560 KB | Output is correct |
4 | Correct | 1307 ms | 77560 KB | Output is correct |
5 | Correct | 424 ms | 77560 KB | Output is correct |
6 | Correct | 261 ms | 77560 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4477 ms | 137028 KB | Output is correct |
2 | Correct | 5466 ms | 137028 KB | Output is correct |
3 | Correct | 3617 ms | 137028 KB | Output is correct |
4 | Correct | 593 ms | 137028 KB | Output is correct |
5 | Correct | 3301 ms | 137028 KB | Output is correct |
6 | Correct | 788 ms | 137028 KB | Output is correct |
7 | Correct | 440 ms | 137028 KB | Output is correct |