結果
問題 | No.788 トラックの移動 |
ユーザー |
![]() |
提出日時 | 2019-02-13 01:49:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 350 ms / 2,000 ms |
コード長 | 2,736 bytes |
コンパイル時間 | 1,644 ms |
コンパイル使用メモリ | 178,312 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-15 07:03:33 |
合計ジャッジ時間 | 4,075 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#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; }