結果
問題 | No.788 トラックの移動 |
ユーザー | ttttan |
提出日時 | 2019-02-10 20:48:06 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 515 ms / 2,000 ms |
コード長 | 2,141 bytes |
コンパイル時間 | 1,730 ms |
コンパイル使用メモリ | 168,796 KB |
実行使用メモリ | 66,176 KB |
最終ジャッジ日時 | 2024-05-08 22:59:08 |
合計ジャッジ時間 | 5,315 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 507 ms
66,048 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 114 ms
19,072 KB |
testcase_05 | AC | 497 ms
66,048 KB |
testcase_06 | AC | 515 ms
66,048 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 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 | 1 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 239 ms
65,920 KB |
testcase_16 | AC | 455 ms
66,176 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:79:13: warning: ‘num’ may be used uninitialized in this function [-Wmaybe-uninitialized] 79 | if(j==num)sum+=(max((ll)0,t[j]-1))*2*d[i][j]; | ^~
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; int main(){ ll inf=1000000000000000000; ll n,m,l;cin>>n>>m>>l; l--; ll cn=0; ll t[n]; for(ll i=0;i<n;i++){ cin>>t[i]; if(t[i]>0)cn++; } if(cn==1){ cout<<0<<endl; return 0; } vector<ll> v[n]; ll cost[n][n]; for(ll i=0;i<n;i++)for(ll j=0;j<n;j++)cost[i][j]=inf; for(ll i=0;i<m;i++){ ll a,b,c;cin>>a>>b>>c; a--;b--; v[a].push_back(b); v[b].push_back(a); cost[a][b]=min(cost[a][b],c); cost[b][a]=min(cost[a][b],c); } for(ll i=0;i<n;i++)cost[i][i]=0; ll d[n][n]; for(ll i=0;i<n;i++)fill(d[i],d[i]+n,inf); for(ll i=0;i<n;i++){ priority_queue<pll,vector<pll>,greater<pll> >q; q.push(make_pair((ll)0,i)); d[i][i]=0; bool used[n];fill(used,used+n,false); while(q.size()>0){ pll p=q.top();q.pop(); ll pf=p.first,ps=p.second; //cout<<ps<<endl; if(used[ps])continue; used[ps]=true; for(ll j=0;j<v[ps].size();j++){ ll now=v[ps][j]; if(used[now])continue; if(d[i][now]>pf+cost[ps][now]){ d[i][now]=pf+cost[ps][now]; q.push(make_pair(d[i][now],now)); } } } } ll ans=inf; for(ll i=0;i<n;i++){ if(i==l){ ll sum=0; for(ll j=0;j<n;j++)sum+=t[j]*2*d[i][j]; ans=min(ans,sum); //cout<<sum<<endl; continue; } ll sum=0; ll num; ll mi=inf; for(ll j=0;j<n;j++){ if(i==j)continue; ll ss=d[l][j]-d[j][i]; if(t[j]==0)ss=d[l][j]+d[j][i]; if(ss<mi){ mi=ss; num=j; } } sum=d[l][num]+d[num][i]; //cout<<sum<<" "; for(ll j=0;j<n;j++){ if(j==num)sum+=(max((ll)0,t[j]-1))*2*d[i][j]; else sum+=t[j]*2*d[i][j]; } ans=min(ans,sum); //cout<<sum<<endl; } cout<<ans<<endl; }