Yuki 160 最短経路のうち辞書順最小 ( Dijkstra )

No.160 最短経路のうち辞書順最小 - yukicoder
なんか前にも書いたような感じがするな.. でもちょっとだけ考えた
経路のリカバリーは終点から一つ前のノードを辿るから、始点と終点を裏返して、同じ距離でたどり着ける場合はその一つ前のノードが小さい方で常に更新。そうすれば必ず辞書順最小となる。

#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
  if( x > v ){
    x = v;
    return 1;
  }
  return 0;
}

signed main(){
  int N, M, S, G; cin >> N >> M >> S >> G;
  vector< vector< pair< int, int > > > E( N );
  for( int i = 0; i < M; ++i ){
    int A, B, C; cin >> A >> B >> C;
    E[ A ].emplace_back( C, B );
    E[ B ].emplace_back( C, A );
  }
  vector< pair< int, int > > dis( N, make_pair( 0x3f3f3f3f, -1 ) );
  priority_queue< tuple< int, int, int >, vector< tuple< int, int, int > >, greater< tuple< int, int, int > > > pq;
  dis[ G ] = make_pair( 0, -1 );
  pq.emplace( 0, -1, G );
  while( not pq.empty() ){
    int d, p, u; tie( d, p, u ) = pq.top(); pq.pop();
    if( make_pair( d, p ) != dis[ u ] ) continue;
    for( int i = 0; i < E[ u ].size(); ++i ){
      int w, v; tie( w, v ) = E[ u ][ i ];
      if( upmin( dis[ v ], make_pair( d + w, u ) ) )
        pq.emplace( d + w, u, v );
    }
  }
  for( int u = S; u != -1; u = dis[ u ].second )
    cout << u << " \n"[ u == G ];
  return 0;
}