1004.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//图的最小圈
#include <iostream>
using namespace std;

const int maxN = 101;
const int maxNum = 0x0f0f0f0f;
int map[maxN+1][maxN+1], map2[maxN+1][maxN+1] ;
int path[maxN+1][maxN+1], c[maxN+1][maxN+1];
int pi, pj, pk;	//记录路径专用
int m, n;
int ans;
void readIn()
{
	int i,a,b,len;
	cin >> m;
	memset( map , 15 , sizeof( map ) );
	for( i = 1; i <= m; i++ )
		{
			cin >> a >> b;
			cin >> len;
			if( map[a][b] > len ) 
				map[b][a] = map[a][b] = len; 
		} 
	memcpy( map2,map,sizeof(map));
}
void floyed()
{
	ans = maxNum;
	int i , j , k;
	pi = 0, pj = 0, pk = 0;
	memset(path, 0 ,sizeof(path));
	memset(c, 0, sizeof(c));
	for ( i = 1 ; i <= n ; i++ )
	{
		for( j = 1 ; j <= n ; j++ )
				for( k = j+1 ; k <= n ; k++ )
				{
					if( k == i )continue;
					if( ans > map2[j][k] + map[j][i] + map[i][k] )
					{
						ans = map2[j][k] + map[j][i] + map[i][k];
						pi = i; pj = j ; pk = k;
						memcpy( path, c, sizeof(c) );
					}
				}
		 
		for( j = 1 ; j <= n ; j++ )
			for( k = j+1 ; k <= n ; k++ )
				if( map2[j][k] > map2[j][i] + map2[i][k] )
				{
					map2[j][k] = map2[k][j] =  map2[j][i] + map2[i][k];
					c[j][k] = c[k][j] = i; 
				}
	}
}
void printPath( int a, int b )
{
	int t = path[a][b];
	if( path[a][t] > 0 ) printPath(a, t);
	cout << t << ' ';
	if( path[t][b] > 0 ) printPath(t, b);
	return;
}
void output()
{	
	if ( ans == maxNum )
		cout << "No solution."<< endl;
	else
	{
		cout << pi << ' ' << pj << ' ';
		if( path[pj][pk] > 0 )printPath(pj, pk);
		cout << pk <<endl;
	} 
}
int main()
{
//	freopen("1004.in","r",stdin);
	while( cin >> n, n!= -1)
	{
		readIn();
		floyed();
		output();
	}
	return 0;
}