无语了……找不到一个能去所有点的点就disjoint
void solve(void)
{
	int i, j, k, m;
	if(N == 1)
	{
		puts("1 0");
		return;
	}
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)
		{
			if(j != i)
			{
				for(k = 0; k < N; k++)
				{
					if(k != i && k != j)
					{
						int temp = dist[i][k] + dist[k][j];
						if(dist[i][k] > 0 && dist[k][j] > 0 && (dist[i][j] < 0 || dist[i][j] > temp))
						{
							dist[i][j] = temp;
						}
					}
				}
			}
		}
	}
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)
		{
			if(i != j && dist[i][j] < 0)
			{
				break;
			}
		}
		if(j < N)//这个点不能所有点都去
		{
			continue;
		}
		for(j = 0; j < N; j++)
		{
			if(j != i && dist[i][j] > dist[i][i])
			{
				dist[i][i] = dist[i][j];//dist[i][i]记最小值
			}
		}
	}
	k = -1;
	m = 0x7FFFFFFF;
	for(i = 0; i < N; i++)
	{
		if(dist[i][i] > 0 && dist[i][i] < m)
		{
			k = i;
			m = dist[i][i];
		}
	}
	if(k >= 0)
	{
		printf("%d %d\n", k + 1, m);
	}
	else
	{
		puts("disjoint");
	}
}

• 我把我的代码发给您了 (1152) TN 2005-04-09 09:55:13
  • 最郁闷的事情发生了，循环顺序搞错了…… (0) frkstyc 2005-04-09 09:59:26
    • 呵呵，Floyd的第一层循环应该是中间节点 (0) TN 2005-04-09 10:00:23