結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー KoshStorm
提出日時 2017-11-17 12:24:33
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 2,843 bytes
コンパイル時間 1,140 ms
コンパイル使用メモリ 30,592 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-25 08:49:32
合計ジャッジ時間 2,007 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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 loINF (long)10000000000
#define shINF (short)10000

/* グローバル */
long 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;			
	long tmp_start,tmp_end;
	short 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 != loINF) && ( tmp_end > tmp_start + tmp_t )){
				#ifdef DEBUG
				printf("頂点 : %d - %d \n",edge[i],edge[i+2*M]);
				printf("tmp_series ==> %ld,%ld,%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("頂点 : %d - %d \n",edge[i],edge[i+2*M]);
					printf("tmp_series ==> %ld,%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 Run\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] = loINF;
		prev[i] = shINF;
	}

	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]); 
		}

	#endif //DEBUG

	ans = bellman_ford(S,G);

	#ifdef DEBUG

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

	#endif //DEBUG

	iter = traceRoute(S,G);

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

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