結果

問題 No.788 トラックの移動
ユーザー sima.tettekesima.tetteke
提出日時 2019-10-07 21:40:05
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,877 bytes
コンパイル時間 1,729 ms
コンパイル使用メモリ 174,852 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 16:48:00
合計ジャッジ時間 4,751 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
ll N, M, L;
ll ans = 0;

vector<vector<pair<ll, ll> > > G;
vector<ll > prever;
 
vector<ll > dijkstra(ll start){
    //準備
    vector<bool > used(N, false);
    vector<ll > dist(N, 1<<28);
    prever.assign(N, -1);
    priority_queue<pair<ll, ll > , vector<pair<ll, ll > >, greater<pair<ll, ll > > > que;
    //初期化
    que.push(make_pair(0, start));
 
    //cout << que.top().first << endl;
 
    while(!que.empty()){
        //距離
        ll d = 0;
        //次の頂点
        ll t_v = 0;
        d = que.top().first;
        t_v = que.top().second;
        //topから削除
        que.pop();
        //探査済みなら処理しない
        if(used[t_v] == true) continue;
        //探査済みにする
        used[t_v] = true;
        //キューの上には既に最小距離が来ているので
        dist[t_v] = d;
        
        //次探査する頂点はt_vなのでt_vから更に次にの頂点の繋がりをキューにいれる
        for(ll i = 0; i < G[t_v].size(); i++){
            //もし探査済みの頂点で，そこまでの累積距離より今更新しようとしている距離が
            //大きいときは更新しない
            ll to = G[t_v][i].first;
            ll cost = d+G[t_v][i].second;
            if(dist[to] <= cost) continue;
            prever[to] = t_v;
            //累積距離と次の頂点
            que.push(make_pair(cost, to));
            //仮dist
            dist[to] = cost;
        }
        //cout << endl;
    }   
    
    return dist;
 
}

vector<ll > get_path(ll t){
    vector<ll > path;
    for(; t != -1; t = prever[t]){
        //cout << prever[t] << endl;
        path.push_back(t);
    }
    //reverse(path.begin(), path.end());
    return path;
}
 
int main() {
    //頂点数
    cin >> N >> M >> L;
    //トラックの数
    vector<ll > T(N, 0);
    for(ll i = 0; i < N; i++){
        cin >> T[i];
    }
    G.assign(N, vector<pair<ll, ll > >());
 
    for(ll i = 0; i < M; i++){   
        ll u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        //双方向に貼りましょうね
        //make_pair(重み,貼りたい辺の先の頂点)
        G[u].push_back(make_pair(v, w));
        G[v].push_back(make_pair(u, w));    
    }

    ll ans = 114514191919;
    for(ll i = 0; i < N; i++){
        ll t_ans = 0;
        vector<ll > dis = dijkstra(i);
        //レッカー車の初期位置以外に集めるとき
        //Lから集積場所まで集めておく
        bool f = false;
        ll tmp_posi = 0;
        if(i != L - 1){
            vector<ll > path = get_path(L - 1);
            //確認
            /*
            for(ll j = 0; j < path.size();j++){
                cout << path[j] + 1 << " ";
            }
            cout << endl;
            */
            for(ll j = 0; j < path.size();j++){
                //cout << path[i] << endl;
                //cout <<  path[j] + 1 << endl;
                if(T[path[j]] > 0){
                    //cout << i + 1 << ":" << path[j] << ":" << dis[L - 1]<< endl;
                    f = true;
                    tmp_posi = path[j];
                    T[path[j]]--;
                    break;
                }
            }
            t_ans += dis[L - 1];
        }
        for(ll j = 0; j < N; j++){
            //最初から集積所のトラックが集まっているので
            if(i == j) continue;
            t_ans += dis[j] * 2 * T[j]; 
        }
        //修正
        if(f == true){
            T[tmp_posi]++;
        }
        ans = min(ans, t_ans);
    }

    cout << ans << endl;
    /*
    dijkstra(0);
    vector<ll > ans = get_path(4);
    for(ll i=0; i < ans.size();i++){
        cout << ans[i]+1 << endl;
    }
    */

    //dijkstra(2);
 
    //cout << ans << endl;
 
}
0