find the mincost route(最短路).cpp

杭电acm解题报告2001---2099.

//问题是求最小花费的环路（注意是环）
//枚举每条边<s,t>，先去掉<s,t>
//再value = Dijkstra(s,t)求出最短路
//判断<s,t> + value是否最小即可
#include <cstdio>
#include <string>

int matrix[110][110],path[110],n,m;          //matrix[][], 30000表示无限大,即无边.否则为有边,其值为边的权值
int Dijkstra(int x,int y)     //起点Vx 终点Vy
{
	int i,j,k,mark[110];
	int min,dist[110];   
	for(i=1;i<=n;i++) {
		mark[i] = 0;
		dist[i] = matrix[x][i];
		path[i] = x;
	}
	mark[x] = 1;     
	do {
		min=0xffffff;
		k=0;
		for(i=1;i<=n;i++)
			if(dist[i]!=-1 && mark[i]==0 && dist[i]<min) {
				min = dist[i];
				k = i;
			}
			if(k) {
				mark[k] = 1;
				for(i=1;i<=n;i++)
                    if(matrix[k][i]!=-1) {
						if(dist[i]==-1 || min+matrix[k][i]<dist[i]) {
							dist[i] = min + matrix[k][i];
							path[i] = k;
						}
                    }
			}
	}while(k);
	return dist[y];
}


int main()
{
	int ans;
	while (scanf("%d %d",&n,&m)==2) {
		memset(matrix,-1,sizeof(matrix));
		for (int i=0;i<m;i++) {
			int a,b,c;
			scanf("%d %d %d",&a,&b,&c);
			if (matrix[a][b] == -1 || matrix[a][b] > c) {
				matrix[a][b] = matrix[b][a] = c;
			}
		}
		ans = 0xffffff;
		for (i=1;i<=n;i++) {
			for (int j=i+1;j<=n;j++) {
				if (matrix[i][j]!=-1) {
					int pre = matrix[i][j];  
					matrix[i][j] = matrix[j][i] = -1;
					int v = Dijkstra(i,j);
					if (v != -1 && v + pre < ans) {
						ans = pre + v;
					}
					matrix[i][j] = matrix[j][i] = pre;
				}
			}
		}
		if (ans == 0xffffff) {
			printf("It's impossible.\n");
		}
		else {
			printf("%d\n",ans);
		}
	}
}