#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXN 102
#define MAX 0xffff
int matrix[MAXN][MAXN], vertex;
int dp[MAXN][MAXN];
int BFS(int startp,int endp)
{
	int p=startp;
	queue<int>q;
	q.push(p);
	memset(dp,0,sizeof(dp));
	while(!q.empty())      
	{
		p=q.front();
		q.pop();
		for(int i=1;i<=vertex;++i)     //搜索每一个可能和p相邻的顶点
		{
			if(i==p )continue;
			if(matrix[i][p])                 //如果有边
			{
				if(dp[startp][i]==0)      //如果是第一次走过来
				{
					dp[startp][i]=dp[startp][p]+matrix[p][i];
					q.push(i);
				}
				else if(dp[startp][i]>dp[startp][p]+matrix[p][i]) //如果已经来过了，检查哪次路径短
				{ 
					dp[startp][i]=dp[startp][p]+matrix[p][i]; 
					q.push(i);   //这时候应该更新状态，不要急着往下走，从i点再走一次，始终保持子路线最短
				}
			}
		}
	}
	return dp[startp][endp];
}
int main()
{
	char s[100];
	while(cin>>vertex)
	{
		for(int i=1;i<=vertex;++i)
		{
			for(int j=1;j<=i;++j)
			{
				if(i==j)matrix[i][j]=0;
				else
				{
					cin>>s;
					if(!strcmp(s,"x"))matrix[i][j]=matrix[j][i]=MAX;
					else matrix[j][i]=matrix[i][j]=atoi(s);
				}
			}
		}
		int ans=0;
		for(int i=2;i<=vertex;++i)
		{
			int t=BFS(1,i);
			if(ans<t)ans=t;
		}
		cout<<ans<<endl;
	}
	return 0;
}

• Re:我竟然用宽搜写了一个，*^◎^* (969) TSERROF 2012-12-02 22:37:45
• 这位同学你好像不小心发明了spfa (0) dram 2015-07-04 19:58:24