結果

問題 No.788 トラックの移動
ユーザー mtsdmtsd
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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