[TIOJ] 1096. E.漢米頓的麻煩

題目連結:http://tioj.infor.org/problems/1096
本題要找最小環,那要怎麼做呢?其實就直接做Floyd-Warshall,然後看哪一組自己到自己最小,大概就這樣吧XD
#include <stdio.h>
#define INF 9999999

int graph[101][101];

int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				scanf("%d",&graph[i][j]);
				if(graph[i][j]==0)graph[i][j]=INF;
			}
		}
		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
					if(graph[i][k]+graph[k][j] < graph[i][j])
						graph[i][j] =graph[i][k]+graph[k][j];
		int min=INF;
		for(int i=0;i<n;i++)
			if(graph[i][i]<min)
				min=graph[i][i];
		if(min==INF)
			puts("-1");
		else
			printf("%d\n",min);
		scanf("%d",&n);
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology