//多源最短路徑,floyd_warshall算法,復(fù)雜度O(n^3)
//求出所有點(diǎn)對(duì)之間的最短路經(jīng),傳入圖的大小和鄰接陣
//返回各點(diǎn)間最短距離min[]和路徑pre[],pre[i][j]記錄i到j(luò)最短路徑上j的父結(jié)點(diǎn)
//可更改路權(quán)類型,路權(quán)必須非負(fù)!
#define MAXN 200
#define inf 1000000000
typedef int elem_t;

void floyd_warshall(int n,elem_t mat[][MAXN],elem_t min[][MAXN],int pre[][MAXN]){
	int i,j,k;
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			min[i][j]=mat[i][j],pre[i][j]=(i==j)?-1:i;
	for (k=0;k<n;k++)
		for (i=0;i<n;i++)
			for (j=0;j<n;j++)
				if (min[i][k]+min[k][j]<min[i][j])
					min[i][j]=min[i][k]+min[k][j],pre[i][j]=pre[k][j];
}