結果
問題 | No.788 トラックの移動 |
ユーザー | YDK1727 |
提出日時 | 2019-03-03 14:12:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 473 ms / 2,000 ms |
コード長 | 1,730 bytes |
コンパイル時間 | 1,751 ms |
コンパイル使用メモリ | 175,780 KB |
実行使用メモリ | 34,816 KB |
最終ジャッジ日時 | 2024-05-08 23:00:20 |
合計ジャッジ時間 | 5,028 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 438 ms
34,688 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 97 ms
11,264 KB |
testcase_05 | AC | 422 ms
34,560 KB |
testcase_06 | AC | 439 ms
34,688 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 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 | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 133 ms
34,816 KB |
testcase_16 | AC | 473 ms
34,688 KB |
ソースコード
#include "bits/stdc++.h" #define ALL(x) x.begin(), x.end() #define LEN(x) (int)x.size() #define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0) using namespace std; typedef int64_t i64; typedef pair<i64,int> pii; template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;} template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;} constexpr int INF = 0x3f3f3f3f; constexpr i64 LINF = 0x3f3f3f3f'3f3f3f3fLL; int N, M, L; int t[2005]; vector<pii> G[2005]; vector<i64> dist[2005]; void dijkstra(int src, vector<i64> &dist) { priority_queue< pii, vector<pii>, greater<pii> > pq; dist.assign(N, LINF); pq.emplace(0, src); dist[src] = 0; while(!pq.empty()) { const i64 c = pq.top().first; const int u = pq.top().second; pq.pop(); if (dist[u] < c) continue; for (const auto &e : G[u]) { const i64 nc = c + e.first; const int nxt = e.second; if (chmin(dist[nxt], nc)) pq.emplace(nc, nxt); } } return; } signed main() { iostreamBooster(); 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; --a, --b; G[a].emplace_back(c, b); G[b].emplace_back(c, a); } for (int src = 0; src < N; ++src) { dijkstra(src, dist[src]); } i64 ans = LINF; for (int goal = 0; goal < N; ++goal) { i64 sum = 0; for (int u = 0; u < N; ++u) sum += 2*dist[goal][u] * t[u]; i64 hoge = sum; for (int k = 0; k < N; ++k) { if (t[k] <= 0) continue; chmin(hoge, sum + dist[L][k] - dist[k][goal]); } chmin(ans, hoge); } cout << ans << endl; return 0; }