我要啦免费统计
/*
    起点到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

*/


http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
posted on 2008-11-06 20:02 阅读(243) 评论(0)  编辑 收藏 引用 所属分类: pku

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理