結果
問題 | No.788 トラックの移動 |
ユーザー | addeight2 |
提出日時 | 2019-02-10 09:44:43 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 492 ms / 2,000 ms |
コード長 | 1,171 bytes |
コンパイル時間 | 1,394 ms |
コンパイル使用メモリ | 167,536 KB |
実行使用メモリ | 34,944 KB |
最終ジャッジ日時 | 2024-05-08 22:58:57 |
合計ジャッジ時間 | 4,629 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 464 ms
34,816 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 | 107 ms
15,232 KB |
testcase_05 | AC | 453 ms
34,816 KB |
testcase_06 | AC | 465 ms
34,816 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 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 | 155 ms
34,688 KB |
testcase_16 | AC | 492 ms
34,944 KB |
ソースコード
#include <bits/stdc++.h> typedef long long ll; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,a) FOR(i,0,a) using namespace std; const int MAX_N=2e3; const ll INF=1e18; struct edge{ int to; ll cst; edge(int t=-1,ll c=0):to(t),cst(c){} }; vector<edge> G[MAX_N]; int N,M,L; ll t[MAX_N]; ll dst[MAX_N][MAX_N]; typedef pair<ll,int> P; void dijk(int s){ REP(v,N)dst[s][v]=INF; dst[s][s]=0; priority_queue<P,vector<P>,greater<P> > pque; pque.push(P(0,s)); while(!pque.empty()){ P p=pque.top(); pque.pop(); int v=p.second; if(p.first>dst[s][v])continue; for(auto e:G[v]){ if(dst[s][e.to]>dst[s][v]+e.cst){ dst[s][e.to]=dst[s][v]+e.cst; pque.push(P(dst[s][e.to],e.to)); } } } } int main(){ cin>>N>>M>>L; L--; REP(i,N)cin>>t[i]; REP(i,M){ int a,b; ll c; cin>>a>>b>>c; a--; b--; G[a].push_back(edge(b,c)); G[b].push_back(edge(a,c)); } REP(i,N){ dijk(i); } ll ans=INF; REP(v,N){ ll sm=0; REP(i,N){ sm+=2*t[i]*dst[v][i]; } REP(u,N){ if(t[u]>0){ ans=min(ans,sm+dst[L][u]-dst[u][v]); } } } int flg=0; REP(v,N){ if(t[v]>0){ flg++; } } if(flg==1){ ans=0; } cout<<ans<<endl; }