結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2015-03-03 22:42:55 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 2,251 bytes |
コンパイル時間 | 1,061 ms |
コンパイル使用メモリ | 106,632 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 01:17:51 |
合計ジャッジ時間 | 2,059 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> using namespace std; template <class T> class EdgeBase { public: int to; T cost; EdgeBase(){}; EdgeBase(int to0, T cost0){to = to0; cost = cost0;} }; typedef EdgeBase<int> Edge; template<class T> void shortestPath(const vector<vector<EdgeBase<T> > >& edges, int start, vector<T>& dist) { const T INF = numeric_limits<T>::max(); const T EPS = static_cast<T>(1.0e-10); dist.assign(edges.size(), INF); dist[start] = 0; priority_queue<pair<T,int>, vector<pair<T,int> >, greater<pair<T,int> > > q; q.push(make_pair(0, start)); while(!q.empty()){ pair<T, int> p = q.top(); q.pop(); int v = p.second; if(dist[v] < p.first - EPS) continue; for(unsigned i=0; i<edges[v].size(); ++i){ EdgeBase<T> e = edges[v][i]; if(dist[v] + e.cost < dist[e.to] - EPS){ dist[e.to] = dist[v] + e.cost; q.push(make_pair(dist[e.to], e.to)); } } } } int main() { int n, m, s, g; cin >> n >> m >> s >> g; vector<vector<Edge> > edges(n); for(int i=0; i<m; ++i){ int a, b, c; cin >> a >> b >> c; edges[a].push_back(Edge(b, c)); edges[b].push_back(Edge(a, c)); } vector<int> dist; shortestPath(edges, s, dist); queue<int> q; vector<int> to(n, INT_MAX); q.push(g); to[g] = -1; while(!q.empty()){ int x = q.front(); q.pop(); for(unsigned i=0; i<edges[x].size(); ++i){ int y = edges[x][i].to; if(dist[y] + edges[x][i].cost == dist[x]){ if(to[y] == INT_MAX) q.push(y); to[y] = min(to[y], x); } } } cout << s; int x = s; while(to[x] != -1){ x = to[x]; cout << ' ' << x; } cout << endl; return 0; }