結果

問題 No.160 最短経路のうち辞書順最小
ユーザー KoshStormKoshStorm
提出日時 2017-11-17 12:03:47
言語 C
(gcc 12.3.0)
結果
RE  
実行時間 -
コード長 2,694 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 30,848 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-25 08:47:53
合計ジャッジ時間 4,735 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 3 ms
6,816 KB
testcase_06 AC 4 ms
6,820 KB
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 WA -
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 AC 1 ms
6,816 KB
testcase_28 AC 5 ms
6,816 KB
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 end,short start){
	/*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 )){
				#ifdef DEBUG
				printf("iの値 ==> %d\n",i);
				printf("tmp_series ==> %d,%d,%d\n",tmp_start,tmp_end,tmp_t);
				#endif

				dis[edge[i+2*M]] = tmp_start + tmp_t;
				prev[edge[i+2*M]] = edge[i];
				update = 1;
			}
			else {if (( tmp_end == tmp_start + tmp_t ) && (prev[edge[i+2*M]] > edge[i])){
				#ifdef DEBUG
					printf("iの値 ==> %d\n",i);
					printf("tmp_series ==> %d,%d,%d\n",tmp_start,tmp_end,tmp_t);
				#endif
				prev[edge[i+2*M]] = edge[i];
				update = 1;
			}}
		}

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

	return dis[end];
}

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

	#ifdef DEBUG
		printf("traceRoute Now\n");
	#endif

	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] = 0;
	}

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

	#ifdef DEBUG

		REP(i,M*6){
			printf("edge[%d] ==> %d\n",i,edge[i]); 
		}

		printf("ans ==> %d\n",ans);

	#endif //DEBUG

	ans = bellman_ford(S,G);

	#ifdef DEBUG
		REP(i,N){
			printf("dis[%d] ==> %d\n",i,dis[i]);
		}
		printf("---------------------------------\n");
		REP(i,N){
			printf("prev[%d] ==> %d\n",i,prev[i]);
		}

	#endif //DEBUG

	iter = traceRoute(S,G);

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