結果

問題 No.160 最短経路のうち辞書順最小
ユーザー KoshStormKoshStorm
提出日時 2017-11-16 20:28:21
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,926 bytes
コンパイル時間 413 ms
コンパイル使用メモリ 29,776 KB
実行使用メモリ 4,508 KB
最終ジャッジ日時 2023-08-16 17:03:20
合計ジャッジ時間 5,184 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 WA -
testcase_28 WA -
testcase_29 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define INF (short)10000

/* グローバル */
short dis[210];  // Nを見積もって入れる	
short edge[20000*6]; // M * 6を見積もって入れる
short prev[210];
short route[210]; // Nを見積もって入れる。
short N;	//頂点数
short M;	//辺の数


short bellman_ford (short start,short end){
	/*startからendへの最短距離を返す*/
	/*配列dis:indexが頂点に対応。始点からの距離を格納する*/
	/*配列edge:辺の情報を持つ。edge[i],edge[i+2*M],edge[i*4*M]が始点,終点,重みに対応している*/
	/* M :辺の数*/

	dis[start] = 0;
	char update;
	short i;			
	short tmp_start,tmp_end,tmp_t;

	while(1){
		update = 0;
		REP(i,2*M){
			tmp_start = dis[edge[i]];
			tmp_end = dis[edge[i+2*M]];
			tmp_t = edge[i+4*M];

			if ((tmp_start != INF) && ( tmp_end > tmp_start + tmp_t )){
				dis[edge[i+2*M]] = tmp_start + tmp_t;
				prev[edge[i+2*M]] = edge[i];
				update = 1;
			}
		}

		if (update == 0){
				break;
			}
	}

	return dis[end];
}

short traceRoute(short start,short end){
	short vertex = end;
	short i = 0;

	while (1){
		route[i] = vertex;
		vertex = prev[vertex];
		i += 1;
		if (vertex == start){
			route[i] = start;
			break;
		}
	}

	return i;
}

int main (void) {
	short ans;
	short S;
	short G;
	short i,iter;
	short f;

	/*入力方法*/
	scanf("%hd",&N);
	scanf("%hd",&M);
	scanf("%hd",&S);	//start
	scanf("%hd",&G);	//end

	
	/*INFで初期化*/
	REP(i,N){	  // NかN+1か注意すること
		dis[i] = INF;
		prev[i] = i;
	}

	REP(i,M){
		f = scanf("%hd%hd%hd",&edge[i],&edge[i+2*M],&edge[i+4*M]);
		edge[i+M] = edge[i];
		edge[i+3*M] = edge[i+2*M];
		edge[i+5*M] = edge[i+4*M];
	}

	ans = bellman_ford(S,G);
	iter = traceRoute(S,G);

	for (i = iter;i >= 0;i--){
		printf("%d ",route[i]);
	}
	printf("\n");

	return 0;

}
0