//單源最短路徑,bellman_ford算法,鄰接陣形式,復雜度O(n^3)
//求出源s到所有點的最短路經(jīng),傳入圖的大小n和鄰接陣mat
//返回到各點最短距離min[]和路徑pre[],pre[i]記錄s到i路徑上i的父結點,pre[s]=-1
//可更改路權類型,路權可為負,若圖包含負環(huán)則求解失敗,返回0
//優(yōu)化:先刪去負邊使用dijkstra求出上界,加速迭代過程
#define MAXN 200
#define inf 1000000000
typedef int elem_t;

int bellman_ford(int n,elem_t mat[][MAXN],int s,elem_t* min,int* pre){
	int v[MAXN],i,j,k,tag;
	for (i=0;i<n;i++)
		min[i]=inf,v[i]=0,pre[i]=-1;
	for (min[s]=0,j=0;j<n;j++){
		for (k=-1,i=0;i<n;i++)
			if (!v[i]&&(k==-1||min[i]<min[k]))
				k=i;
		for (v[k]=1,i=0;i<n;i++)
			if (!v[i]&&mat[k][i]>=0&&min[k]+mat[k][i]<min[i])
				min[i]=min[k]+mat[pre[i]=k][i];
	}
	for (tag=1,j=0;tag&&j<=n;j++)
		for (tag=i=0;i<n;i++)
			for (k=0;k<n;k++)
				if (min[k]+mat[k][i]<min[i])
					min[i]=min[k]+mat[pre[i]=k][i],tag=1;
	return j<=n;
}