結果

問題 No.807 umg tours
ユーザー ugis_progugis_prog
提出日時 2019-03-23 20:53:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 600 ms / 4,000 ms
コード長 1,665 bytes
コンパイル時間 844 ms
コンパイル使用メモリ 77,480 KB
実行使用メモリ 27,860 KB
最終ジャッジ日時 2024-05-02 23:42:09
合計ジャッジ時間 7,605 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 296 ms
16,708 KB
testcase_12 AC 321 ms
16,660 KB
testcase_13 AC 423 ms
19,912 KB
testcase_14 AC 175 ms
11,012 KB
testcase_15 AC 135 ms
9,168 KB
testcase_16 AC 428 ms
20,880 KB
testcase_17 AC 600 ms
26,880 KB
testcase_18 AC 556 ms
26,920 KB
testcase_19 AC 543 ms
23,756 KB
testcase_20 AC 324 ms
16,064 KB
testcase_21 AC 347 ms
16,512 KB
testcase_22 AC 135 ms
9,088 KB
testcase_23 AC 104 ms
7,680 KB
testcase_24 AC 315 ms
25,024 KB
testcase_25 AC 578 ms
27,860 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