Dijikstra tree を求める問題． Dijikstra 法は，最短経路を求めるアルゴリズムよりも高性能で， 最短木を求めるアルゴリズム である．
実装
普通に Dijikstra をして，直前の遷移するときの edge を記録しておけば Dijikstra tree が手に入る．
注意: 遷移したとき， \(if(dis[cu] != cd) continue; \) を入れないと TLE.
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
struct Edge{
ll to, cost, id;
Edge(ll to, ll cost , ll id) : to(to), cost(cost), id(id){}
};
int main() {
ll n, m ;
cin >> n >> m;
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a, --b;
ed[a].push_back(Edge(b,c,i));
ed[b].push_back(Edge(a,c,i));
}
min_priority_queue<pll> q;
vll ans(n,-1);
vll dis(n, INFL);
q.push({0,0});
chmin(dis[0], 0LL);
while(q.size()){
auto [cd, cv] = q.top(); q.pop();
if(dis[cv] != cd) continue; // 無いと TLE
for(auto [nv, nco, ni] : ed[cv]){
ll nd = cd + nco;
if(chmin(dis[nv], nd)){
q.push({nd, nv});
ans[nv] = ni;
}
}
}
srep(i,1,n){
cout << ans[i]+1 << endl;
}
return 0;
}
