本文主要是介绍最短路径(Dijkstra)-HDU 1874-畅通工程续，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-
最短路径(Dijkstra)-HDU 1874-畅通工程续
-
题目链接：
畅通工程续
-
题目基础：
最短路径-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;elsecout<<Short_Path[T]<<endl;}return 0;
}
这篇关于最短路径(Dijkstra)-HDU 1874-畅通工程续的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
