結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2020-07-25 18:14:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 1,251 bytes |
コンパイル時間 | 3,314 ms |
コンパイル使用メモリ | 204,600 KB |
最終ジャッジ日時 | 2025-01-12 05:36:54 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:39:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 39 | int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:42:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 42 | int u,v,c; scanf("%d%d%d",&u,&v,&c); | ~~~~~^~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; template<class T> struct edge{ int to; T wt; edge(int to,const T& wt):to(to),wt(wt){} }; template<class T> using weighted_graph=vector<vector<edge<T>>>; template<class T> void add_undirected_edge(weighted_graph<T>& G,int u,int v,const T& wt){ G[u].emplace_back(v,wt); G[v].emplace_back(u,wt); } template<class T> vector<T> Dijkstra(const weighted_graph<T>& G,int s){ constexpr T INF=numeric_limits<T>::max(); int n=G.size(); vector<T> d(n,INF); d[s]=0; priority_queue<pair<T,int>> Q; Q.emplace(0,s); while(!Q.empty()){ T d0=-Q.top().first; int u=Q.top().second; Q.pop(); if(d0>d[u]) continue; for(const auto& e:G[u]){ int v=e.to; if(d[v]>d[u]+e.wt) d[v]=d[u]+e.wt, Q.emplace(-d[v],v); } } return d; } int main(){ int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); weighted_graph<int> G(n); rep(i,m){ int u,v,c; scanf("%d%d%d",&u,&v,&c); add_undirected_edge(G,u,v,c); } auto d=Dijkstra(G,t); vector<int> ans={s}; for(int u=s;u!=t;){ int next=n; for(auto e:G[u]) if(d[u]==d[e.to]+e.wt) next=min(next,e.to); u=next; ans.emplace_back(u); } rep(i,ans.size()) printf("%d%c",ans[i],i+1<ans.size()?' ':'\n'); return 0; }