結果
問題 | No.1812 Uribo Road |
ユーザー | MasKoaTS |
提出日時 | 2022-01-09 16:01:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 186 ms / 5,000 ms |
コード長 | 2,714 bytes |
コンパイル時間 | 4,806 ms |
コンパイル使用メモリ | 269,300 KB |
実行使用メモリ | 9,360 KB |
最終ジャッジ日時 | 2024-04-26 19:48:45 |
合計ジャッジ時間 | 7,899 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 10 ms
6,656 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | AC | 6 ms
5,376 KB |
testcase_10 | AC | 4 ms
5,376 KB |
testcase_11 | AC | 4 ms
5,376 KB |
testcase_12 | AC | 73 ms
8,448 KB |
testcase_13 | AC | 29 ms
8,320 KB |
testcase_14 | AC | 30 ms
8,192 KB |
testcase_15 | AC | 98 ms
5,672 KB |
testcase_16 | AC | 49 ms
5,760 KB |
testcase_17 | AC | 162 ms
7,424 KB |
testcase_18 | AC | 61 ms
7,716 KB |
testcase_19 | AC | 186 ms
9,344 KB |
testcase_20 | AC | 186 ms
9,344 KB |
testcase_21 | AC | 173 ms
9,336 KB |
testcase_22 | AC | 171 ms
9,360 KB |
testcase_23 | AC | 5 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 31 ms
5,376 KB |
testcase_26 | AC | 4 ms
5,376 KB |
testcase_27 | AC | 46 ms
5,820 KB |
testcase_28 | AC | 49 ms
5,760 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 8 ms
5,376 KB |
testcase_31 | AC | 110 ms
8,064 KB |
testcase_32 | AC | 3 ms
5,376 KB |
testcase_33 | AC | 44 ms
7,604 KB |
ソースコード
#include <math.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, l, n) for (int i = (l); i < (n); i++) #define ite(i, a) for(auto& i : a) #define all(x) x.begin(), x.end() #define lb lower_bound #define ub upper_bound #define lbi(A, x) (ll)(lb(all(A), x) - A.begin()) #define ubi(A, x) (ll)(ub(all(A), x) - A.begin()) using ll = long long; using Pair = pair<int, int>; template <class T> using V = vector<T>; template <class T> using VV = V<V<T> >; const ll INF = 1000000000000000001; const int inf = 2000000000; const ll mod = 1000000007; const ll MOD = 998244353; template <class T> inline V<T> getList(int n) { V<T> res(n); rep(i, 0, n) { cin >> res[i]; }return res; } template <class T> inline VV<T> getGrid(int m, int n) { VV<T> res(m, V<T>(n)); rep(i, 0, m) { res[i] = getList<T>(n); }return res; } inline V<int> dtois(string& s) { V<int> vec = {}; for (auto& e : s) { vec.push_back(e - '0'); } return vec; } V<int> dijkstra(int s, int n, VV<Pair>& route) { V<int> dist(n, -1); priority_queue<Pair, V<Pair>, greater<Pair> > pq; pq.push({ 0,s }); int cnt = 0; while (pq.size() and cnt < n) { Pair p = pq.top(); pq.pop(); int d = p.first; int v = p.second; if (dist[v] == -1) { dist[v] = d; cnt++; rep(j, 0, route[v].size()) { Pair p = { d + route[v][j].second,route[v][j].first }; pq.push(p); } } } return dist; } int main(void) { int n, m, k; cin >> n >> m >> k; V<int> r(k); rep(i, 0, k) { cin >> r[i]; r[i]--; } VV<Pair> route(n, V<Pair>(0)); VV<int> edge(m, V<int>(3)); rep(i, 0, m) { rep(j, 0, 3) { cin >> edge[i][j]; } edge[i][0]--; edge[i][1]--; route[edge[i][0]].push_back({ edge[i][1],edge[i][2] }); route[edge[i][1]].push_back({ edge[i][0],edge[i][2] }); } VV<int> dist(n, V<int>(0)); set<int> st = { 0,n - 1 }; ite(i, r) { st.insert(edge[i][0]); st.insert(edge[i][1]); } for (auto itr = st.begin(); itr != st.end(); itr++) { auto i = *itr; dist[i] = dijkstra(i, n, route); } V<VV<int> > dp(1 << k, VV<int>(k, V<int>(2, inf))); rep(i, 0, k) { rep(j, 0, 2) { dp[1 << i][i][j] = dist[0][edge[r[i]][j ^ 1]] + edge[r[i]][2]; } } rep(bit, 1, 1 << k) { rep(s, 0, k) { if (((bit >> s) & 1) == 0) { continue; } rep(t, 0, k) { if ((bit >> t) & 1) { continue; } rep(x, 0, 2) { rep(y, 0, 2) { int b = bit | (1 << t); dp[b][t][y] = min(dp[b][t][y], dp[bit][s][x] + dist[edge[r[s]][x]][edge[r[t]][y ^ 1]] + edge[r[t]][2]); } } } } } int ans = inf; rep(i, 0, k) { rep(j, 0, 2) { ans = min(ans, dp[(1 << k) - 1][i][j] + dist[edge[r[i]][j]][n - 1]); } } cout << ans << endl; return 0; }