結果

問題 No.807 umg tours
コンテスト
ユーザー ugis_prog
提出日時 2019-03-23 20:53:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 568 ms / 4,000 ms
コード長 1,665 bytes
コンパイル時間 876 ms
コンパイル使用メモリ 77,860 KB
実行使用メモリ 27,864 KB
最終ジャッジ日時 2024-11-23 19:20:26
合計ジャッジ時間 7,492 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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