結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー alpha_virginis
提出日時 2015-03-02 01:56:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,462 bytes
コンパイル時間 602 ms
コンパイル使用メモリ 65,656 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-24 01:00:10
合計ジャッジ時間 6,607 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

int main() {
  int n, m, s, g;
  int t1, t2, t3;
  int i, j, k;
  bool b;

  int cost[256][256] = {};
  int next[256][256] = {};

  std::cin >> n >> m >> s >> g;

  for(i = 0; i < n; i++) {
    for(j = 0; j < n; j++) {
      next[i][j] = -1;
      cost[i][j] = -1;
    }
  }
  
  for(i = 0; i < m; i++) {
    std::cin >> t1 >> t2 >> t3;
    cost[t1][t2] = t3;
    next[t1][t2] = t2;
    cost[t2][t1] = t3;
    next[t2][t1] = t1;
  }    

  for(;;) {
    b = true;
    for(i = 0; i < n; i++) {
      for(j = 0; j < n; j++) {
	if(i == j) {
	  continue;
	}
	for(k = 0; k < n; k++) {
	  if(i == k || j == k) {
	    continue;
	  }
	  if( cost[i][k] != -1 && cost[k][j] != -1 ) {
	    if( cost[i][j] == -1 || cost[i][j] > cost[i][k] + cost[k][j] ) {
	      b = false;
	      next[i][j] = k;
	      cost[i][j] = cost[i][k] + cost[k][j];
	      continue;
	    }
	    if( cost[i][j] == cost[i][k] + cost[k][j] ) {
	      if( next[i][j] > k ) {
		b = false;
		next[i][j] = k;
		cost[i][j] = cost[i][k] + cost[k][j];
		continue;
	      }
	    }
	  }
	}
      }
    }
    if( b ) {
      break;
    }
  }

  t1 = s;
  printf("%d", t1);
  for(;;) {
    t2 = next[t1][g];
    for(;;) {
      if( t2 == next[t1][t2] ) {
	break;
      }
      t2 = next[t1][t2];
    }
    t1 = t2;
    printf(" %d", t1);
    if(t1 == g) {
      break;
    }  
  }
  printf("\n");
  
  return 0;
}
0