hdu 3790 最短路径问题最短路Dijkstra-白红宇

hdu 3790 最短路径问题最短路Dijkstra

阅读量：4073 次

发布时间：2019-05-25

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

做图论的都是上辈子折翼的天使。。。有点难想，但若有明确的思路，程序很好打

清除所有点的标号

设d[0]=0,其他d[i]=INF

循环n次

{

在所以未标号结点中，选出d值最小的节点x

标记节点x

对于从x出发的所有边（x，y), 更新d[y]=min(d[y],d[x]+w(x,y));

}

错了几次

第一次把路程和金钱分开处理了，很快查出来

第二次又错了，但心想这是模板题，怎么错了，一看discuss,重边。。哭了。。

打的时候发现了很多问题

假如INF==1<<31-1

memset(a,INF,sizeof(a)); 初始都为0.。。

而0x1f==31

memset(a,0x1f,sizeof(a))后，初始都为522133279.

memset(a,0x1f1f1f1f,sizeof(a))后，初始都为522133279.

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=1010;const int INF=0x1f1f1f1f;int dislen[maxn];int discost[maxn];int w[maxn][maxn];int ss[maxn][maxn];bool visit[maxn];int n,m;int s,t;int main(){    while(scanf("%d",&n)!=EOF)    {        scanf("%d",&m);        if(n==0&&m==0)            break;        int i,j;        memset(visit,true,sizeof(visit));        memset(w,0x1f,sizeof(w));        memset(ss,0x1f,sizeof(ss));        int u,v,len,cost;      //  for(i=1; i<=n; i++)       // {        //    w[i][i]=0;        //    ss[i][i]=0;       // }       for(i=1;i
       
        len||w[u][v]==len&&ss[u][v]>cost)            {                w[u][v]=len;                w[v][u]=len;                ss[u][v]=cost;                ss[v][u]=cost;            }        }        scanf("%d%d",&s,&t);            for(i=1; i<=n; i++)            {                if(i==s)                {                    dislen[i]=0;                    discost[i]=0;                }                else                {                    dislen[i]=w[s][i];                    discost[i]=ss[s][i];                }            }            for(j=1; j<=n; j++)            {                int x;                int minn=INF;                for(i=1; i<=n; i++)                {                    if(visit[i]==true&&dislen[i]
        
         dislen[x]+w[x][i]) { dislen[i]=dislen[x]+w[x][i]; discost[i]=discost[x]+ss[x][i]; } else if(visit[i]==true&&dislen[i]==dislen[x]+w[x][i]&&ss[x][i]+discost[x]