はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

GRL_1_C All Pairs Shortest Path

問題
全点対間最短経路 | グラフ | Aizu Online Judge

全ての点の最短経路を求める問題です。GRL_1_Bでやったベルマンフォード法をそのまま全点でやるコードを書いたのですが、ダメでした。
原因はGRL_1_Bで実装したベルマンフォード法が間違えてたっぽいです。GRL_1_Bではacceptされるのですが、GRL_1_Cのテストケースではwrongとなってしまいました。再度考え直します。

今回はワーシャルフロイド法を実装しました。
最短経路といえばダイクストラって思ってたのですが、ワーシャルフロイド法が一番分かり易いアルゴリズムですね。
下記のブログを参考にしました。
ワーシャルフロイド法とその例題 - ゆらのふなびと

#include<stdio.h>
#define INF 2000000000
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int d[100][100];
int V,E;

int WarshallFloyd(){
	for(int k=0;k<V;k++){
		for(int i=0;i<V;i++){
			if(d[i][k]!=INF){
				for(int j=0;j<V;j++){
					if(d[k][j]!=INF){
						d[i][j]=MIN(d[i][j],d[i][k]+d[k][j]);
						if(j==k && d[j][k]<0){
							printf("NEGATIVE CYCLE\n");
							return 1;
						}
					}
				}
			}
		}
	}
	return 0;
}

int main(){
	int s,t,cost;
	int i,j;
	
	scanf("%d %d",&V,&E);
	
	for(i=0;i<V;i++){
		for(j=0;j<V;j++){
			if(i==j)d[i][j]=0;
			else d[i][j]=INF;
		}
	}
	
	for(i=0;i<E;i++){
		scanf("%d %d %d",&s,&t,&cost);
		d[s][t]=cost;
	}
	
	if(WarshallFloyd())return 0;
	
	for(i=0;i<V;i++){
		for(j=0;j<V;j++){
			if(j==V-1){
				if(d[i][j]==INF)printf("INF\n");
				else printf("%d\n",d[i][j]);
			}
			else {
				if(d[i][j]==INF)printf("INF ");
				else printf("%d ",d[i][j]);
			}
		}
	}
	
	return 0;
}

if(d[i][k]!=INF)とif(d[k][j]!=INF)で、i→k→jの道がないところを省いています。ここに苦労しました。
しかしグラフむずい。