题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为正值。
请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示1号点到n号点的最短距离。
如果路径不存在,则输出-1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例
3 3
1 2 2
2 3 1
1 3 4
输出样例
3
思路
Dijkstra算法算是贪心思想实现的,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离
本题要求我们求出从1号点到n号点的最短距离,也就是需要我们来求解dist[n]的最小值。
通过一步步的求出从1到各个点的最小值,也就是数组dist的所有的值,即可求出结果
如何求dist:
因为要求最小值,所以先将数组初始化为极大值,
从1开始,对于每一个点i,访问1~n每个点k,如果当前访问的点没有被访问过,并且距离更小,就存入,直到把所有n个点遍历完之后得到的就是最短的对于的点,即点i到起点的最短路径
每次找到最小距离对应的点k时,都要更新disdis[j]=min(dis[j],dis[k]+g[k][j])
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=505;
int n,m;
int g[N][N];//存储邻接矩阵
int dis[N]; //记录当前点与第一个点之间的距离
int vis[N]; //标记是否已经被选过
int dijkstra()
{
memset(dis,0x3f,sizeof(dis));//本题要求最小值,初始化为极大值
dis[1]=0;//第一个点是起始点,距离为0
for(int i=1;i<=n;i++){
int k=0;//存访问的点
for(int j=1;j<=n;j++){
if(!vis[j] && (k==0 || dis[j]<dis[k])){//这个点没有被选过 并且( 是刚开始找点或者距离更小)
k=j; // 把当前访问的点存下来
}
}
vis[k]=1;// 最终选择的下一个点 标记已选
for(int j=1;j<=n;j++){//找到了距离最小的点k,并用最小的点k去更新其他的点到起点的距离
dis[j]=min(dis[j],dis[k]+g[k][j]);
}
}
if(dis[n]==0x3f3f3f3f){//最终一个点到第一个点的距离无穷大,即不存在最短路径
return -1;
}
else{
return dis[n];//第n个点到第一个点之间的距离
}
}
int main()
{
cin >> n >> m;
memset(g,0x3f,sizeof(g));//初始化为无穷大
while(m--){
int x,y,z;
cin >> x >> y >> z;
g[x][y]=min(g[x][y],z);//有可能有重边,取最小的边长
}
cout << dijkstra() << endl;
return 0;
}