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;
}
```