最短路径(Dijkstra)-HDU 1874-畅通工程续

电玩女神 2022-05-14 03:37 179阅读 0赞

*  # 最短路径(Dijkstra)-HDU 1874-畅通工程续 #

--------------------

*  ## 题目链接： ##

### [畅通工程续][Link 1] ###

*  ## 题目基础： ##

### [最短路径-Dijkstra(迪杰斯特拉)算法][-Dijkstra] ###

*  ## 思路： ##

### 题目大意： ###

略略略

### 题解： ###

可能都有个习惯，一篇算法两篇水题

就说下**怎样判断 S-T之间有无最短路：bool Vis 是用于标记加入最短路的标记数组，如果顶点a在最短路，那么Vis\[a\]=true，所以，*如果Vis\[T\]=false ,说明最短路不存在***

*  ## 代码： ##

#include <iostream>
    #include<memory.h>
    using namespace std;
    #define MAX_SIZE 1024
    #define INF 65535
    
    //邻接图
    struct MGrapth
    {
        int Vexs[MAX_SIZE];  //顶点表
        int Arc[MAX_SIZE][MAX_SIZE];  //邻接矩阵
        int Num_Vertext,Num_Edges;  //顶点数，边数
    };
    MGrapth Map;
    
    int Path[MAX_SIZE];   /*表示路径 Path[i]->i*/
    int Short_Path[MAX_SIZE]; /*Start->i 的最短路径和*/
    bool Vis[MAX_SIZE];   /*当前最短路径结点true*/
    
    void Init(int n,int m)
    {
        memset(Vis,0,sizeof(Vis));
        memset(Path,0,sizeof(Path));
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                Map.Arc[i][j]=INF;
        Map.Num_Vertext=n;
        Map.Num_Edges=m;
    }
    
    void Dijkstra(int Start)
    {
        int v,w,k,Min;
        for(v=0;v<Map.Num_Vertext;v++)
            Short_Path[v]=Map.Arc[Start][v];  /*Start到相连结点的距离*/
    
        Short_Path[Start]=0;   /*Start->Start 的距离为0*/
        Vis[Start]=1;   /*Start为当前最短路径结点*/
    
        for(v=1;v<Map.Num_Vertext;v++)
        {
            Min=INF;
            for(w=0;w<Map.Num_Vertext;w++)
            {
                if(!Vis[w]&&Short_Path[w]<Min)
                {
                    k=w;
                    Min=Short_Path[w];
                }
            }
    
            Vis[k]=true; /*找出最短路到散点的最小值，将该散点连入最短路*/
    
            for(w=0;w<Map.Num_Vertext;w++)  /*更新最短路*/
            {
                if(!Vis[w]&&Min+Map.Arc[k][w]<Short_Path[w])  /*图中某点到v0的距离比当前路短，更新*/
                {
                    Short_Path[w]=Min+Map.Arc[k][w];
                    Path[w]=k;
                }
            }
        }
    }
    
    
    int main()
    {
        int N,M;
        int A,B,X;
        int S,T;
        while(cin>>N>>M)
        {
            Init(N,M);
            for(int i=0;i<M;i++)
            {
                cin>>A>>B>>X;
                if(Map.Arc[A][B]>X)
                    Map.Arc[A][B]=X;
                if(Map.Arc[B][A]>X)
                    Map.Arc[B][A]=X;
            }
            cin>>S>>T;
            Dijkstra(S);
            if(!Vis[T])
                cout<<"-1"<<endl;
            else
                cout<<Short_Path[T]<<endl;
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1874
[-Dijkstra]: https://blog.csdn.net/SZU_Crayon/article/details/82290234