結果
問題 |
No.807 umg tours
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }