#include <iostream>
#include <string.h>

using namespace std;

typedef int Graph[1001][1001];

Graph g;

int Dijkstra(Graph G,int n,int s,int t,int path[])
{
	int i,j,w,minc,d[1001],mark[1001];
	for(i=0;i<n;i++)
	{
		mark[i]=0;
	}
	for(i=0;i<n;i++)
	{
		d[i]=G[s][i];
		path[i]=s;
	}
	mark[s]=1;path[s]=0;d[s]=0;
	for(i=1;i<n;i++)
	{
		minc=0;
		w=0;
		for(j=0;j<n;j++)
		{
			if((mark[j]==0)&&(minc<d[j]))
			{
				minc=d[j];
				w=j;
			}
		}
		mark[w]=1;
		for(j=0;j<n;j++)
		{
			if(mark[j]==0&&G[w][j]!=0&&d[j]<((d[w]<G[w][j])?d[w]:G[w][j]))
			{
				d[j]=(d[w]<G[w][j])?d[w]:G[w][j];
				path[j]=w;
			}
		}
	}
	return d[t];
}

int main()
{
	int ncase,n,m,i,j,k,l,r,p[1001];
	cin>>ncase;
	for(i=1;i<=ncase;i++)
	{
		cin>>n>>m;
		memset(g,0,sizeof(g));
		for(j=0;j<m;j++)
		{
			cin>>k>>l;
			cin>>g[k-1][l-1];
			g[l-1][k-1]=g[k-1][l-1];
		}
		r=Dijkstra(g,n,0,n-1,p);
		cout<<"Scenario #"<<i<<":"<<endl;
		cout<<r<<endl<<endl;
	}
	return 0;
}

• Dijkstra实质是距离标号法，这个你可以看成 瓶颈标号 (瓶颈就是一条路是权值最小边的权值） 贪心时每次找标号最大 (2) Liuzhaoliang 2010-01-26 18:51:09