結果
問題 | No.788 トラックの移動 |
ユーザー | tottoripaper |
提出日時 | 2019-02-13 01:49:57 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 386 ms / 2,000 ms |
コード長 | 2,736 bytes |
コンパイル時間 | 1,927 ms |
コンパイル使用メモリ | 177,240 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-08 22:59:42 |
合計ジャッジ時間 | 4,723 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 385 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 88 ms
5,376 KB |
testcase_05 | AC | 378 ms
5,376 KB |
testcase_06 | AC | 386 ms
5,376 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 | 76 ms
5,376 KB |
testcase_16 | AC | 359 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) #define thd(t) std::get<2>(t) #define unless(p) if(!(p)) #define until(p) while(!(p)) using ll = std::int64_t; using P = std::tuple<int,int>; int N, M, L; int t[2100]; std::vector<P> G[2100]; int dist[2100]; std::priority_queue<P, std::vector<P>, std::greater<P>> pq; bool used[2100]; void dijkstra(int s){ std::fill(dist + 1, dist + 1 + N, std::numeric_limits<int>::max()); dist[s] = 0; pq.emplace(0, s); until(pq.empty()){ int v, d; std::tie(d, v) = pq.top(); pq.pop(); if(d > dist[v]){ continue; } for(auto &e : G[v]){ int w, c; std::tie(w, c) = e; if(dist[w] > d + c){ dist[w] = d + c; pq.emplace(dist[w], w); } } } } int f1(int v){ used[v] = true; int res = 0; if(t[v] > 0){ res = v; } for(auto &e : G[v]){ int w, c; std::tie(w, c) = e; if(!used[w] && dist[w] == dist[v] + c){ int u = f1(w); if(u > 0 && dist[u] > dist[res]){ res = u; } } } return res; } int f2(int v){ used[v] = true; if(t[v] > 0){ return v; } int res = 0; for(auto &e : G[v]){ int w, c; std::tie(w, c) = e; if(!used[w] && dist[v] == dist[w] + c){ int u = f2(w); if(u > 0 && dist[u] > dist[res]){ res = u; } } } return res; } int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cin >> N >> M >> L; for(int i=1;i<=N;++i){ std::cin >> t[i]; } if(std::count_if(t + 1, t + 1 + N, [](int x){return x > 0;}) <= 1){ std::cout << 0 << std::endl; return 0; } for(int i=0;i<M;++i){ int a, b, c; std::cin >> a >> b >> c; G[a].emplace_back(b, c); G[b].emplace_back(a, c); } ll minDist = std::numeric_limits<ll>::max(); for(int i=1;i<=N;++i){ // 頂点 i にトラックを集める dijkstra(i); ll d = 0; memset(used, 0, sizeof(used)); int v = f1(L); if(v > 0){ d = 2ll * dist[v] - dist[L]; t[v] -= 1; }else{ d = dist[L]; v = f2(L); if(v > 0){ t[v] -= 1; } } for(int j=1;j<=N;++j){ d += 2ll * t[j] * dist[j]; } minDist = std::min(minDist, d); if(v > 0){ t[v] += 1; } } std::cout << minDist << std::endl; }