#include <iostream>
#include <math.h>
using namespace std;
int hash[205];
int map[2005][2005];
bool visit[2005];
long long  dp[25][205][205];
long long dp2[25][205];   //走k步从起点走到i点的最短路径
int sp;
int Min (int a,int b)
{
	return a<b?a:b;
}
void init(int n,int s,int e)
{
	int i,j;
	memset(dp,5,sizeof(dp));
	for(i=0;i<sp;i++)
	{
		for(j=0;j<sp;j++)
		{
			if(map[hash[i]][hash[j]]<1005)dp[0][i][j]=map[hash[i]][hash[j]];
		}
	}
	memset(dp2,5,sizeof(dp2));
}
long long work(int n,int s,int e)
{
	int k,i,j,kk,temp,tempn;
	for(k=1;(1<<k)<=n;k++)
	{
		for(i=0;i<sp;i++)
		{
			for(j=0;j<sp;j++)
			{
				for(kk=0;kk<sp;kk++)
					dp[k][i][j]=Min(dp[k][i][j],dp[k-1][i][kk]+dp[k-1][kk][j]);
			}
		}
	}
	for(i=0;i<sp;i++)if(hash[i]==s)break;
	for(j=0;j<sp;j++)if(hash[j]==e)break;
	if((1<<(k-1))==n)return dp[k-1][i][j];
	temp=0;
	tempn=n;
	while(tempn%2==0)
	{
		temp++;
		tempn/=2;
	}
	for(j=0;j<sp;j++)
	{
		dp2[temp][j]=Min(dp2[temp][j],dp[temp][i][j]);
	}
	k=temp+1;
	for(;(1<<k)<n;k++)
	{
		if(n&(1<<k))
		{
			for(i=0;i<sp;i++)
			{
				for(j=0;j<sp;j++)
				{
					dp2[k][j]=Min(dp2[k][j],dp2[k-1][i]+dp[k][i][j]);
				}
			}
		}
		else
		{
			for(i=0;i<sp;i++)dp2[k][i]=dp2[k-1][i];
		}
	}
	for(i=0;i<sp;i++)if(hash[i]==e)break;
	return dp2[k-1][i];
}
int main ()
{
	int n,t,s,e,i,a,b,c;
	while(scanf("%d%d%d%d",&n,&t,&s,&e)!=EOF)
	{
		memset(visit,0,sizeof(visit));
		memset(map,127,sizeof(map));
		sp=0;
		for(i=0;i<t;i++)
		{
			scanf("%d%d%d",&c,&a,&b);
			if(visit[a]==0)
			{
				hash[sp++]=a;
				visit[a]=1;
			}
			if(visit[b]==0)
			{
				hash[sp++]=b;
				visit[b]=1;
			}
			if(map[a][b]<c)continue;
			map[a][b]=c;
			map[b][a]=c;
		}
		init(n,s,e);
		printf("%lld\n",work(n,s,e));
	}
	return 0;
}

• Re:求解,这个为什么错阿????????///////................,,,,,,,,,,,,,,,,, (1839) huxinjie800 2010-08-06 22:59:18