結果

問題 No.788 トラックの移動
コンテスト
ユーザー ttttan
提出日時 2019-02-10 20:48:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 476 ms / 2,000 ms
コード長 2,141 bytes
コンパイル時間 1,781 ms
コンパイル使用メモリ 169,968 KB
実行使用メモリ 66,176 KB
最終ジャッジ日時 2024-12-15 07:03:00
合計ジャッジ時間 4,689 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
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];
      |             ^~

ソースコード

diff # 

#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;
}
0