結果
問題 |
No.807 umg tours
|
ユーザー |
|
提出日時 | 2019-03-23 00:29:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 745 ms / 4,000 ms |
コード長 | 2,083 bytes |
コンパイル時間 | 2,235 ms |
コンパイル使用メモリ | 226,752 KB |
最終ジャッジ日時 | 2025-01-07 00:08:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #include <unordered_set> using namespace std; #define ll long long #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++) #define revrep(i,n) for(int (i)=(n)-1;i>=0; i--) // example const ll inf=1e15; void dijkstra(int s, map<int,map<int,ll>>& g, vector<vector<ll>>& dist,const ll inf, const ll zero) { int n=dist[0].size(); vector<vector<bool>> visited = vector<vector<bool>>(2, vector<bool>(n)); fill(dist[0].begin(),dist[0].end(),inf); fill(dist[1].begin(),dist[1].end(),inf); using P = tuple<ll,int,int>; priority_queue<P,vector<P>, greater<P>> pq; dist[0][s]=zero; dist[1][s]=zero; //visited[s]=true; pq.push(make_tuple(0,s,0)); pq.push(make_tuple(0,s,1)); while(!pq.empty()) { int v,b; ll d; tie(d,v,b)=pq.top(); pq.pop(); if(visited[b][v]) continue; visited[b][v]=true; for(auto& uw : g[v]) { int u; ll w; tie(u,w)=uw; if(b==0) { if(visited[0][u])continue; if(d<dist[1][u]) { dist[1][u]=d; pq.push(make_tuple(dist[1][u],u,1)); } if(d+w<dist[0][u]) { dist[0][u]=d+w; pq.push(make_tuple(dist[0][u],u,0)); } } else { // b=1 if(visited[1][u]) continue; if(d+w<dist[1][u]) { dist[1][u]=d+w; pq.push(make_tuple(dist[1][u],u,1)); } } } } } void dfs(int s, vector<ll>& min_c, vector<vector<int>>& ng,map<int,map<int,ll>>& g) { // we have min_c[s] for(auto& u : ng[s]) { min_c[u]=min(min_c[s],g[s][u]); dfs(u,min_c,ng,g); } } int main() { cin.tie(0); ios::sync_with_stdio(false); cout<<setprecision(std::numeric_limits<float>::max_digits10); int n,m; cin>>n>>m; map<int,map<int,ll>> g; rep(i,m) { ll a,b,c; cin>>a>>b>>c; g[a-1][b-1]=c; g[b-1][a-1]=c; } vector<vector<ll>> dist = vector<vector<ll>>(2,vector<ll>(n)); const ll inf=1e15; dijkstra(0,g,dist,inf,0LL); rep(i,n) { cout << dist[0][i]+dist[1][i]<<endl; } return 0; }