結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
|
提出日時 | 2015-03-04 06:24:26 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 48 ms / 5,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 2,163 ms |
コンパイル使用メモリ | 175,364 KB |
実行使用メモリ | 9,288 KB |
最終ジャッジ日時 | 2024-06-24 01:23:09 |
合計ジャッジ時間 | 2,902 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct Dist { int cost; vector<int> path; bool operator<(const Dist& other) const { if(cost != other.cost){ return cost < other.cost; } return path < other.path; } bool operator>(const Dist& other) const { return (other < *this); } Dist operator+(const Dist& other) const { Dist res = *this; res.cost += other.cost; res.path.insert(res.path.end(), other.path.begin(), other.path.end()); return res; } }; typedef vector<vector<Dist>> Graph; Dist dijkstra(const Graph &g, int S, int G){ const int V = g.size(); vector<Dist> dist(V, {1 << 25}); dist[S] = {0, {S}}; priority_queue<Dist, vector<Dist>, greater<Dist>> Q; Q.push({0, {S}}); while(!Q.empty()){ auto d = Q.top(); Q.pop(); auto pos = d.path.back(); if(dist[pos] < d){ continue; } for(const auto& e : g[pos]){ auto nd = d + e; auto npos = e.path.back(); if(nd < dist[npos]){ dist[npos] = nd; Q.push(nd); } } } return dist[G]; } int main(){ int N, M, S, G; cin >> N >> M >> S >> G; vector<vector<Dist>> g(N); for(int i=0;i<M;i++){ int a, b, c; cin >> a >> b >> c; g[a].push_back(Dist{c, {b}}); g[b].push_back(Dist{c, {a}}); } auto res = dijkstra(g, S, G); for(int v : res.path){ cout << v << " "; } return 0; }