/**//*
起點(diǎn)到n點(diǎn) 路徑上 所能承受的 最大重量的車
dist[k] 源點(diǎn)到k 路徑中最小的那個(gè)邊權(quán)值 mat[k][i]邊k-i權(quán)值
取路徑 dist[k] 和mat【k】【i】邊最大那個(gè) 更新 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++)//估計(jì)計(jì)距離最小的頂點(diǎn)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
爬 閱讀(261)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
pku