> DIJ结构不变,然后每次寻找在X集合中到Y集合中最长的边,再更新DIST(如果COST[V][W]>DIST[W] 那么更新DIST)
> 谁可以教教我这样做对不对?
> 程序如下:
> #include <stdio.h>
> #include <memory.h>
> #include <string.h>
> #define true  1
> #define false 0
> #define I  -9999
> int cost[200][20];
> int dist[200];
> int v0,v1;
> int Teams=0,Index[200];
> char Name[200][100];
> 
> int GetID(char *NowName)
> {
> 	int i,j,k,b;
> 	i = -1;j = Teams;
> 	while (i < j-1)
> 	{
> 		k = (i+j)/2;
> 		b = strcmp(Name[Index[k]],NowName);
> 		if (!b)
> 		{
> 			return Index[k];
> 		}
> 		if (b>0)
> 		{
> 			j=k;
> 		}
> 		else
> 		{
> 			i=k;
> 		}
> 	}
> 	for (i=Teams;i>j;i--)
> 	{
> 		Index[i]=Index[i-1];
> 	}
> 
> 	Index[j]=Teams;
> 	strcpy(Name[Teams],NowName);
> 
> 	Teams++;
> 	return Teams-1;
> }
> 
> void main()
> {
> 	int final[200], i,j, v, v1,w,max,min,d,n,m,num=0;
> 	char name[200],start[100],end[100];
> 	int x,y,distance,load[100];
> 
> 	while(1)
> 	{
> 
> 		num++;
> 		scanf("%d%d", &n,&m);
> 		if(n==0&&m==0)break;
> 		memset(load,0,sizeof(int)*n);
> 		for(i = 0; i < m; i++)
> 		{
> 			scanf("%s",name);
> 			x=GetID(name);
> 			scanf("%s", name);
> 			y=GetID(name);
> 			scanf("%d", &distance);
> 			cost[x][y]=distance;
> 			cost[y][x]=distance;
> 		}
> 		scanf("%s %s",start,end);
> 		d=GetID(end);
> 		v0=GetID(start);
> 		for(i=0;i<n;i++)
> 			for(j=0;j<n;j++)
> 			{
> 				if(cost[i][j]==0)cost[i][j]=I;
> 
> 			}
> 		for (v = 0; v < n; v++)
> 		{
> 			final[v] = false;
> 			dist[v] = cost[v0][v];
> 		}
> 
> 
> 		final[v0] = true;
> 		load[v0]=-I;
> 		v=v0;
> 		for(i=1;i<n;i++)
> 		{
> 			max = I;
> 
> 			v1=v;
> 			for (w=0;w<n;w++)
> 			{
> 				if (!final[w]&&dist[w]>max)
> 				{
> 					max=dist[w];
> 					v=w;
> 				}
> 			}
> 			final[v]=true;
> 			if(max<load[v1])load[v]=max;
> 			else load[v]=load[v1];
> 			for (w=0;w<n;w++)
> 			{
> 				if(!final[w]&&(cost[v][w]>dist[w]))
> 				{
> 					dist[w]=cost[v][w];
> 				}
> 			}
> 		}
> 		printf("Scenerio #%d\n",num);
> 		printf("%d tons\n\n",load[d]);
> 	}
> }