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