結果
問題 | No.788 トラックの移動 |
ユーザー |
![]() |
提出日時 | 2019-02-08 22:08:55 |
言語 | C++11 (gcc 8.5.0) |
結果 |
AC
|
実行時間 | 453 ms / 2,000 ms |
コード長 | 2,210 bytes |
コンパイル時間 | 928 ms |
使用メモリ | 3,688 KB |
最終ジャッジ日時 | 2023-01-08 05:09:15 |
合計ジャッジ時間 | 4,654 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 使用メモリ |
---|---|---|
testcase_00 | AC | 421 ms
3,688 KB |
testcase_01 | AC | 1 ms
3,400 KB |
testcase_02 | AC | 1 ms
3,476 KB |
testcase_03 | AC | 1 ms
3,340 KB |
testcase_04 | AC | 96 ms
3,572 KB |
testcase_05 | AC | 408 ms
3,472 KB |
testcase_06 | AC | 420 ms
3,592 KB |
testcase_07 | AC | 1 ms
3,344 KB |
testcase_08 | AC | 1 ms
3,400 KB |
testcase_09 | AC | 2 ms
3,268 KB |
testcase_10 | AC | 2 ms
3,264 KB |
testcase_11 | AC | 2 ms
3,392 KB |
testcase_12 | AC | 2 ms
3,488 KB |
testcase_13 | AC | 2 ms
3,404 KB |
testcase_14 | AC | 2 ms
3,328 KB |
testcase_15 | AC | 94 ms
3,580 KB |
testcase_16 | AC | 453 ms
3,472 KB |
ソースコード
#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <utility> #include <queue> #include <set> #include <map> #include <deque> #include <iomanip> #include <cstdio> #include <stack> #include <numeric> using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define PB push_back #define inf 1e+16 #define rep(i,n) for(int i=0;i<(int)(n);++i) vector<vector<pair<ll,int> > > g; int main(){ int n,m,s; cin >> n >> m >> s; vector<ll> dd(n,inf); vector<ll> t(n); int cnt=0; rep(i,n){ cin >> t[i]; if(t[i]>0)cnt++; } if(cnt==1){ cout << 0 << endl; return 0; } s--; g.resize(n); rep(i,m){ int a,b,c; cin >> a >> b >> c; a--;b--; g[a].push_back(MP(c,b)); g[b].push_back(MP(c,a)); } dd[s] = 0; priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >pq; pq.push(MP(0,s)); while(!pq.empty()){ auto x = pq.top(); pq.pop(); if(dd[x.second]!=x.first)continue; for(auto y:g[x.second]){ if(dd[y.second]>dd[x.second]+y.first){ dd[y.second] = dd[x.second]+y.first; pq.push(MP(dd[y.second],y.second)); } } } ll ans = inf; for(int i=0;i<n;i++){ pq.push(MP(0,i)); vector<ll> d(n,inf); d[i] = 0; while(!pq.empty()){ auto x = pq.top(); pq.pop(); if(d[x.second]!=x.first)continue; for(auto y:g[x.second]){ if(d[y.second]>d[x.second]+y.first){ d[y.second] = d[x.second]+y.first; pq.push(MP(d[y.second],y.second)); } } } ll tmp = 0; rep(j,n){ tmp += 2*d[j]*t[j]; } ll ma = -inf; rep(j,n){ if(t[j]>0){ ma = max(ma,d[j]-dd[j]); } } tmp -= ma; //cerr << tmp << endl; ans = min(ans,tmp); } cout << ans << endl; return 0; }