1695_magazine delivery.cpp

来自「总共80多道题的POJ详细解题报告」· C++ 代码 · 共 39 行

#include<iostream.h>
#include<memory.h>
int m,n,graph[30][30],dis[30][30][30] ;
int D(int a,int b,int c )
{
	int tmp,d1,d2,d3 ;
	if ( c == m ) return 0;
    if ( dis[b][c][c+1] == 0 ) dis[b][c][c+1] = D(b,c,c+1) ;
	if ( dis[a][b][c+1] == 0 ) dis[a][b][c+1] = D(a,b,c+1) ;
	if ( dis[a][c][c+1] == 0 ) dis[a][c][c+1] = D(a,c,c+1) ;
	d1 = dis[b][c][c+1] + graph[a][c+1] ;
	d2 = dis[a][b][c+1] + graph[c][c+1] ;
	d3 = dis[a][c][c+1] + graph[b][c+1] ;
    if ( d2 > d1 ) tmp = d1;
	else tmp = d2;
	if ( tmp > d3 ) tmp = d3 ;
	return tmp;
}
void main()
{
	int i,j,v;
	cin >> n ;
	while(n--)
	{
		cin >> m;
		memset( graph,0,sizeof(graph));
		for( i = 0 ; i < m-1; i++ )
		{
			for( j = i+1; j < m ; j++ )
			{
				cin >> graph[i][j] ;
				graph[j][i] = graph[i][j];
			}
		}
		memset( dis,0,sizeof(dis)) ;
		cout << D(0,0,0) << endl;
	}
}