結果
問題 | No.788 トラックの移動 |
ユーザー | uenoku |
提出日時 | 2020-04-24 13:08:03 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 521 ms / 2,000 ms |
コード長 | 2,277 bytes |
コンパイル時間 | 1,845 ms |
コンパイル使用メモリ | 182,336 KB |
実行使用メモリ | 34,816 KB |
最終ジャッジ日時 | 2024-05-08 23:03:36 |
合計ジャッジ時間 | 5,228 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 484 ms
34,816 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 107 ms
11,136 KB |
testcase_05 | AC | 476 ms
34,816 KB |
testcase_06 | AC | 479 ms
34,688 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 169 ms
34,688 KB |
testcase_16 | AC | 521 ms
34,688 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; void YESNO(bool), YesNo(bool); template <class T1, class T2> bool chmin(T1 &l, const T2 &r); template <class T1, class T2> bool chmax(T1 &l, const T2 &r); struct dijkstra { using lli = long long int; vector<vector<pair<lli, lli>>> e; int n; lli inf = 1e18; dijkstra(int n) : n(n) { e.resize(n); } void add(int a, int b, lli c) { e[a].push_back(make_pair(b, c)); } void biadd(int a, int b, lli c) { add(a, b, c); add(b, a, c); } vector<lli> get(int s) { vector<lli> dist(n, inf); dist[s] = 0; using p = pair<lli, lli>; priority_queue<p, vector<p>, greater<p>> que; que.push(make_pair(0, s)); while (!que.empty()) { lli d = que.top().first; lli cur = que.top().second; que.pop(); if (dist[cur] < d) continue; dist[cur] = d; for (auto s : e[cur]) { lli wei = s.second; lli to = s.first; if (dist[to] > dist[cur] + wei) { dist[to] = dist[cur] + wei; que.push(make_pair(dist[cur] + wei, to)); } } } return dist; } }; int main() { // N^2logM lli n, m, l; cin >> n >> m >> l; l--; vector<lli> t(n); rep(i, n) cin >> t[i]; dijkstra dij(n); int a, b, c; rep(i, m) { cin >> a >> b >> c; dij.biadd(a - 1, b - 1, c); } lli ret = 1e18; vector<vector<lli>> mat; rep(i, n) mat.push_back(dij.get(i)); rep(i, n) { // l -> k -> i でkで拾う lli cost = 0; rep(j, n) cost += mat[i][j] * 2 * t[j]; lli ans = cost; rep(k, n) { lli dist = mat[l][k] + mat[k][i]; if (t[k]) { chmin(ans, dist + cost - 2 * mat[i][k]); } } chmin(ret, ans); } cout << ret << endl; } // -- lib void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; } void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; } template <class T1, class T2> bool chmin(T1 &l, const T2 &r) { return (l > r) ? (l = r, true) : false; } template <class T1, class T2> bool chmax(T1 &l, const T2 &r) { return (l < r) ? (l = r, true) : false; }