結果

問題 No.160 最短経路のうち辞書順最小
ユーザー 0w1
提出日時 2016-11-27 20:42:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 1,064 bytes
コンパイル時間 1,713 ms
コンパイル使用メモリ 183,392 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 12:18:26
合計ジャッジ時間 2,687 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0