結果

問題 No.160 最短経路のうち辞書順最小
ユーザー alpha_virginisalpha_virginis
提出日時 2015-03-02 23:35:21
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 127 ms
5,376 KB
testcase_05 AC 145 ms
5,376 KB
testcase_06 AC 152 ms
5,376 KB
testcase_07 AC 164 ms
5,376 KB
testcase_08 AC 165 ms
5,376 KB
testcase_09 AC 126 ms
5,376 KB
testcase_10 AC 170 ms
5,376 KB
testcase_11 AC 173 ms
5,376 KB
testcase_12 AC 171 ms
5,376 KB
testcase_13 AC 161 ms
5,376 KB
testcase_14 AC 156 ms
5,376 KB
testcase_15 AC 165 ms
5,376 KB
testcase_16 AC 141 ms
5,376 KB
testcase_17 AC 174 ms
5,376 KB
testcase_18 AC 164 ms
5,376 KB
testcase_19 AC 128 ms
5,376 KB
testcase_20 AC 128 ms
5,376 KB
testcase_21 AC 168 ms
5,376 KB
testcase_22 AC 170 ms
5,376 KB
testcase_23 AC 161 ms
5,376 KB
testcase_24 AC 138 ms
5,376 KB
testcase_25 AC 166 ms
5,376 KB
testcase_26 AC 165 ms
5,376 KB
testcase_27 AC 150 ms
5,376 KB
testcase_28 AC 76 ms
5,376 KB
testcase_29 AC 132 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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