HDOJ2544

浅浅的花香味﹌ 2022-06-08 03:29 112阅读 0赞

题目：[http://acm.hdu.edu.cn/showproblem.php?pid=2544][http_acm.hdu.edu.cn_showproblem.php_pid_2544]

***最短路径问题：（迪杰斯特拉）算法，也可以用Floyed等算法，我自己用了Floyed，也可以用Dijkstra。***

**1.Floyed**

#include<iostream>
    using namespace std;
    int main()
    {
        int N,M,A,B,C,d[101][101],i,j,k;
        while(cin>>N>>M)
        {
            if(N==0&&M==0)break;
            for(i=1;i<=N;i++)
              for(j=1;j<=N;j++)
                d[i][j]=100000000;
            while(M--)
            {
              cin>>A>>B>>C;
              if(d[A][B]>C)d[A][B]=d[B][A]=C;
            }
            for(k=1;k<=N;k++)
             for(i=1;i<=N;i++)
              for(j=1;j<=N;j++)
               d[i][j]=(d[i][j]<(d[i][k]+d[k][j]))?d[i][j]:(d[i][k]+d[k][j]);
               cout<<d[1][N]<<endl;
        }
        return 0;
    }

**2.Dijkstra**

#include<iostream>
    using namespace std;
    int main()
    {
        bool flag[101];
        int map[101][101],i,j,k,dis[101],min;
        int N,M,A,B,C;
        while(cin>>N>>M&&N&&M)//注意可以用这种方法当两个输入为0时要跳出的情况
        {
            for(i=1;i<=N;i++)
              for(j=1;j<=N;j++)
                map[i][j]=100000000;
            while(M--)
            {
                cin>>A>>B>>C;
                if(map[A][B]>C)map[A][B]=map[B][A]=C;
            }
            for(i=1;i<=N;i++)
             {
                 dis[i]=map[1][i];
                 flag[i]=true;//true表示需要寻找一个最短路径，false表示已经是最短路径
             }
             flag[i]=false;
             for(i=2;i<=N;i++)
             {
                 min=100000000;//记录最短路径值
                 for(j=2;j<=N;j++)
                 {
                     if(flag[j]&&dis[j]<min)
                     {
                         k=j;
                         min=dis[j];
                     }
                     flag[k]=false;
                     for(j=2;j<=N;j++)
                     {
                         if(flag[j]&&dis[k]+min[k][j]<dis[j])
                         dis[j]=dis[k]+min[k][j];
                     }
                 }
             }
             cout<<dis[N]<<endl;
        }
        return 0;
    }

这两个程序我都编译过并试过，并且都AC的，不信你可以先试试。

[http_acm.hdu.edu.cn_showproblem.php_pid_2544]: http://acm.hdu.edu.cn/showproblem.php?pid=2544