結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 159 ms
6,944 KB
testcase_05 AC 176 ms
6,940 KB
testcase_06 AC 182 ms
6,944 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 158 ms
6,940 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 207 ms
6,944 KB
testcase_15 AC 215 ms
6,944 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 160 ms
6,944 KB
testcase_20 AC 160 ms
6,940 KB
testcase_21 WA -
testcase_22 AC 219 ms
6,940 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 198 ms
6,940 KB
testcase_28 AC 75 ms
6,940 KB
testcase_29 AC 170 ms
6,940 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;
	      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