就是Floyd求最短路径。

//2121184  	2010-03-22 10:18:01  	  Wrong Answer  	1221  	C++  	0  	184
/*错误在于输出的时候先输入the number of country pairs that follow，
然后再输出Test Set #1  
*/
//2121193  	2010-03-22 10:23:26  	  Accepted  	1221  	C++  	0  	184
#include <iostream>
#include  <cstdio>      
#include  <cstdlib>       
#include   <climits>   
using namespace std;
#define   MAXSIZE   22           

#define   MAXSUM(a, b)   (((a) != INT_MAX && (b) != INT_MAX) ?  ((a) + (b)) : INT_MAX) 
#define SWAP(a, b)  { temp = a; a = b; b = temp; }

int dist[MAXSIZE][MAXSIZE];
const int n = 20;

void floyd()   
{   
	int  i, j, k;     
	for (k = 1; k <= n; k++)     
		for (i = 1; i <= n; i++)    
			for (j = 1; j <= n; j++)     
			if (dist[i][j] > MAXSUM(dist[i][k], dist[k][j]))    
			{      
				dist[i][j] = MAXSUM(dist[i][k], dist[k][j]);   
			}   
}   
bool readin()   
{   
	int i, j;
	int cnt, b;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n;j++)
		{
			dist[i][j] = INT_MAX;
			if(i == j)
				dist[i][j] = 0;
		}
	for(i = 1; i < n; i++)
	{
		if(scanf("%d", &cnt) == EOF)
			return false;
		while(cnt--)
		{
			scanf("%d", &b);
			dist[i][b] = dist[b][i] = 1;
		}
	}
	return true;
} 

int main(void)   
{   
	int m;
	int a, b;
	int T = 1;
	while(readin())
	{
		floyd();
		scanf("%d", &m);
		printf("Test Set #%d\n", T++);
		while(m-- && scanf("%d%d", &a, &b))
			printf("%d to %d: %d\n",a, b, dist[a][b]);
		printf("\n");
	}
   return 0;
}

• 相关文章
• 全局相关文章