# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
30927 | 2017-08-01T06:44:02 Z | Navick | Cities (BOI16_cities) | C++14 | 4000 ms | 41804 KB |
#include <bits/stdc++.h> #define F first #define S second #define pii pair<int, int> #define pb push_back using namespace std; typedef long long ll; typedef long double ld; const int N = 1e5 + 10, K = 5; const ll INF = 1e18; ll dp[N][1 << K]; vector<pii> adj[N]; set<pair<ll, int> > s; int imp[K]; int main(){ int n, k, m; scanf("%d %d %d", &n, &k, &m); for(int i=0; i<k; i++){ int v; scanf("%d", &v); imp[i] = v; } for(int i=0; i<m; i++){ int u, v, w; scanf("%d %d %d", &u, &v, &w); adj[u].pb({v, w}); adj[v].pb({u, w}); } for(int mask=1; mask<(1 << k); mask++){ s.clear(); for(int i=1; i<=n; i++){ dp[i][mask] = INF; for(int t=mask; t; t=mask & (t - 1)) dp[i][mask] = min(dp[i][mask], dp[i][t] + dp[i][mask ^ t]); s.insert({dp[i][mask], i}); } if(__builtin_popcount(mask) == 1){ for(int j=0; j<k; j++) if(mask & (1 << j)) dp[imp[j]][mask] = 0; } while(!s.empty()){ int v = (*s.begin()).S; s.erase(s.begin()); for(auto X : adj[v]){ int u = X.F, w = X.S; if(dp[u][mask] > dp[v][mask] + w){ s.erase({dp[u][mask], u}); dp[u][mask] = dp[v][mask] + w; s.insert({dp[u][mask], u}); } } } } ll res = INF; for(int i=1; i<=n; i++) res = min(res, dp[i][(1 << k) - 1]); printf("%lld\n", res); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 29368 KB | Output is correct |
2 | Correct | 0 ms | 29368 KB | Output is correct |
3 | Correct | 0 ms | 29368 KB | Output is correct |
4 | Correct | 0 ms | 29368 KB | Output is correct |
5 | Correct | 0 ms | 29368 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2106 ms | 41644 KB | Output is correct |
2 | Correct | 1903 ms | 41804 KB | Output is correct |
3 | Correct | 783 ms | 38740 KB | Output is correct |
4 | Correct | 99 ms | 33724 KB | Output is correct |
5 | Correct | 736 ms | 41644 KB | Output is correct |
6 | Correct | 93 ms | 33724 KB | Output is correct |
7 | Correct | 6 ms | 29500 KB | Output is correct |
8 | Correct | 3 ms | 29500 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 29500 KB | Output is correct |
2 | Correct | 13 ms | 29500 KB | Output is correct |
3 | Correct | 6 ms | 29500 KB | Output is correct |
4 | Correct | 6 ms | 29500 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4000 ms | 41644 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4000 ms | 41644 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |