/**//*
起点到n点 路径上 所能承受的 最大重量的车
dist[k] 源点到k 路径中最小的那个边权值 mat[k][i]边k-i权值
取路径 dist[k] 和mat【k】【i】边最大那个 更新 dist[i]
*/
#include<iostream>
using namespace std;
#define MAXN 1002
#define inf 1000000000
typedef int elem_t;
int mat[MAXN][MAXN];
int dist[MAXN];
void dijkstra(int n,int s)
{
int v[MAXN],i,j,k;
for (i=0;i<n;i++)
dist[i]=mat[s][i],v[i]=0;//初始化
for (dist[s]=0,j=0;j<n;j++){
for (k=-1,i=0;i<n;i++)//估计计距离最小的顶点k
if (!v[i]&&(k==-1||dist[i] > dist[k]))
k=i;
for (v[k]=1,i=0;i<n;i++)
if (!v[i] && mat[k][i]>0&& min(dist[k],mat[k][i]) > dist[i])
{
dist[i]=min(dist[k],mat[k][i]);
}
}
}
int main()
{
int cases;
int n,m,k,x1,y1;
cin>>cases;
for(int i = 1;i <= cases;i ++){
cin>>n>>m;
memset(mat,0,sizeof(mat));
for(int j=0;j<m;j++){
cin>>x1>>y1>>k;
mat[x1-1][y1-1]=k;
mat[y1-1][x1-1]=k;
dijkstra(n,0);
cout<<"Scenario #"<<i<<":"<<endl;
cout<<dist[n-1]<<endl<<endl;
}
return 0;
}
/**//*
1
3 3
1 2 3
1 3 4
2 3 5
*/
posted on 2008-11-06 20:02
爬 阅读(256)
评论(0) 编辑 收藏 引用 所属分类:
pku