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]);
	}
}

• 大家帮忙看看? (2097) Essence_me 2005-08-15 11:17:36
  • 常见的trick：平行边，不知道你考虑了没有？ (0) xfxyjwf 2005-08-15 11:24:49
    • 不懂,我没有遇见过,可以说得详细一些吗? (0) Essence_me 2005-08-15 11:26:24
      • 两条边连接的顶点相同，而费用不同 (0) xfxyjwf 2005-08-15 11:27:11
        • 55555555555还存在这种东西,,被........阴了.再看看... (0) Essence_me 2005-08-15 11:37:12
          • 这种东西，很常见啊。 (0) xfxyjwf 2005-08-15 11:38:27
            • 改了,还是WA..... (0) Essence_me 2005-08-15 11:44:19
              • Re:改了,还是WA..... (13) sladhu 2006-03-03 19:53:05
• 异形？ (2097) achilles 2005-08-15 12:01:33