結果

問題 No.160 最短経路のうち辞書順最小
ユーザー alpha_virginis
提出日時 2015-03-02 23:35:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 174 ms / 5,000 ms
コード長 1,546 bytes
コンパイル時間 563 ms
コンパイル使用メモリ 64,816 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-24 01:12:24
合計ジャッジ時間 5,411 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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;
	      t2 = next[i][k];
	      for(;;) {
		if( t2 == next[i][t2] ) {
		  break;
		}
		t2 = next[i][t2];
	      }
	      next[i][j] = t2;
	      cost[i][j] = cost[i][k] + cost[k][j];
	      continue;
	    }
	    if( cost[i][j] == cost[i][k] + cost[k][j] ) {
	      t2 = next[i][k];
	      for(;;) {
		if( t2 == next[i][t2] ) {
		  break;
		}
		t2 = next[i][t2];
	      }
	      if( next[i][j] > t2 ) {
		b = false;
		next[i][j] = t2;
		continue;
	      }
	    }
	  }
	}
      }
    }
    if( b ) {
      break;
    }
  }

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