結果

問題 No.807 umg tours
ユーザー ugis_progugis_prog
提出日時 2019-03-23 20:53:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 592 ms / 4,000 ms
コード長 1,665 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 80,004 KB
実行使用メモリ 28,068 KB
最終ジャッジ日時 2023-08-15 12:15:58
合計ジャッジ時間 8,048 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 295 ms
17,268 KB
testcase_12 AC 337 ms
16,652 KB
testcase_13 AC 449 ms
19,780 KB
testcase_14 AC 180 ms
10,884 KB
testcase_15 AC 134 ms
9,224 KB
testcase_16 AC 450 ms
20,604 KB
testcase_17 AC 592 ms
27,128 KB
testcase_18 AC 588 ms
26,808 KB
testcase_19 AC 559 ms
24,732 KB
testcase_20 AC 340 ms
16,124 KB
testcase_21 AC 352 ms
16,632 KB
testcase_22 AC 139 ms
9,268 KB
testcase_23 AC 103 ms
7,696 KB
testcase_24 AC 303 ms
25,548 KB
testcase_25 AC 590 ms
28,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define int long long
using P = pair<int,int>;

struct edge{ int to,cost; };

vector<vector<int>> dijkstra(vector<vector<edge>>& Graph,int vertex, int start, int tickets){
    #define INF 1e18
    using PP = pair<int,P>;
    #define weight first
    #define now second.first
    #define ticket second.second

    vector<vector<int>> dist(vertex,vector<int>(tickets+1,INF));
    priority_queue<vector<PP>,vector<PP>,greater<PP>> Q;

    Q.push({0,{start,tickets}});
    for(int i=0;i<=tickets;i++) dist[start][i] = 0;

    while(!Q.empty()){
        PP p = Q.top(); Q.pop();
        
        if(dist[p.now][p.ticket] < p.weight) continue;

        for(edge Edge : Graph[p.now]){
            if(dist[Edge.to][p.ticket] < p.weight + Edge.cost) continue;
            
            dist[Edge.to][p.ticket] = p.weight + Edge.cost;
            Q.push({dist[Edge.to][p.ticket], {Edge.to,p.ticket}});

            if(p.ticket > 0){
                if(dist[Edge.to][p.ticket-1] < p.weight) continue;
                dist[Edge.to][p.ticket-1] = p.weight;
                Q.push({dist[Edge.to][p.ticket-1], {Edge.to,p.ticket-1}});
            }
        }
    }
    
    return dist;
}


signed main(){
    int N,M;
    cin >> N >> M;
    vector<vector<edge>> Graph(N);

    for(int i=0;i<M;i++){
        int from,to,weight;
        cin >> from >> to >> weight;
        from--, to--;

        Graph[from].push_back({to,weight});
        Graph[to].push_back({from,weight});
    }

    auto dist = dijkstra(Graph,N,0,1);
    for(int i=0;i<N;i++) cout << dist[i][1] + dist[i][0] << endl;
}
0