結果
問題 | No.788 トラックの移動 |
ユーザー |
|
提出日時 | 2019-02-08 22:29:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 419 ms / 2,000 ms |
コード長 | 1,310 bytes |
コンパイル時間 | 1,811 ms |
コンパイル使用メモリ | 174,684 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-15 07:00:13 |
合計ジャッジ時間 | 4,707 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> P; int N, M, L, T[2000]; vector<P> edges[2000]; vector<int64_t> dijkstra(int s){ vector<int64_t> dist(N); for(int i=0; i<N; i++) dist[i] = (i==s ? 0 : 1e18); priority_queue<P, vector<P>, greater<P>> que; que.push({0, s}); while(que.size()){ auto p = que.top(); que.pop(); int d = p.first, i = p.second; if(dist[i] < d) continue; for(auto& e : edges[i]){ int j = e.first, d2 = e.second + d; if(dist[j] > d2){ dist[j] = d2; que.push({d2, j}); } } } return dist; } int main(){ cin >> N >> M >> L; L--; for(int i=0; i<N; i++) cin >> T[i]; for(int i=0; i<M; i++){ int a, b, c; cin >> a >> b >> c; edges[a-1].push_back({b-1, c}); edges[b-1].push_back({a-1, c}); } auto distL = dijkstra(L); int64_t ans = 1e18; for(int s=0; s<N; s++){ auto dist = dijkstra(s); int64_t result = 0, save = 0; for(int i=0; i<N; i++) result += dist[i] * 2 * T[i]; for(int i=0; i<N; i++) if(T[i] > 0) save = max(save, dist[i] - distL[i]); ans = min(ans, result - save); } cout << ans << endl; return 0; }