本文共 713 字，大约阅读时间需要 2 分钟。

题意：卡车从路上经过，给出顶点 n , 边数 m,然后是a点到b点的权值w（a到b路段的承重）,求卡车最重的重量是多少可以从上面经过。

思路：求所有路径中的最小的边的最大值。可以用迪杰斯特拉算法，只需要将模板的路径更新那改一下，具体看代码注释。

注意：数组的初始化为-1或零m因为题意说的权值并不是距离，而是路的承重。

代码如下：

#include
   
    #include
    
     #include
     
      using namespace std;int e[1010][1010],inf=0x3f3f3f3f,n,dis[1010],book[1010];void djstl(int x){    for(int i=1; i<=n; i++)        dis[i]=e[1][i];    memset(book,0,sizeof(book));    book[x]=1;    for(int i=1; i<=n-1; i++)    {        int maxx=-1,u;        for(int j=1; j<=n; j++)        {            if(dis[j]>maxx&&!book[j])            {                u=j;                maxx=dis[j];            }        }        book[u]=1;//找到最短的边        for(int v=1; v<=n; v++)        {            if(dis[v]
     
    
   

转载地址：http://jgsl.baihongyu.com/