yukicoder 160 最短経路のうち辞書順最小
問題
方針
まずゴールから各頂点への最短距離を求め,スタートからゴールまで順にたどっていく. 定石通り,辞書順の条件を満たすために,今いる頂点からの移動先を,移動可能なもののうち番号が最も小さいものを選ぶ. $u$ から隣接する $v$ へ移動可能か,つまり最短経路の一部になりうるかは $dist(s,v) = dist(s,u) + dist(u,v)$ かどうかで判定する.
実装
typedef int Weight;
struct Edge {
int src, dst;
Weight weight;
Edge(int src_, int dst_, Weight weight_) :
src(src_), dst(dst_), weight(weight_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
int const inf = 1e8;
// あり本のダイクストラ法
vector<int> dijkstra(Graph const & g, int s, int t){
swap(s,t);
typedef tuple<Weight,int> State;
priority_queue<State> q;
int n = g.size();
vector<Weight> dist(n, inf);
vector<int> prev(n,-1);
dist[s] = 0;
q.emplace(0,s);
while (q.size()) {
Weight d;
int v;
tie(d,v) = q.top(); q.pop();
d *= -1;
if (dist[v] < d) continue;
for(auto & e : g[v]){
if (dist[e.dst] > dist[v] + e.weight) {
dist[e.dst] = dist[v] + e.weight;
q.emplace(-dist[e.dst], e.dst);
}
}
}
int cur = t;
vector<int> path {t};
while(cur != s){
int nx_v = inf;
for(auto & e : g[cur]){
if(dist[cur] == dist[e.dst] + e.weight){
nx_v = min(nx_v, e.dst);
}
}
cur = nx_v;
path.pb(cur);
}
return path;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N,M,S,G;
cin >> N >> M >> S >> G;
Graph g(N);
rep(i,M){
int a,b,c;
cin >> a >> b >> c;
g[a].eb(a,b,c);
g[b].eb(b,a,c);
}
vi path = dijkstra(g,S,G);
rep(i,path.size()){
cout << path[i] << (i+1==(int)path.size() ? '\n' : ' ');
}
}