题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。
输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。
如果路径不存在,则输出 −1。
数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0,且不超过 10000。
样例
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
堆优化版dijkstra算法
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int p=1000010;
typedef pair<int,int>PII;
int h[p],e[p],ne[p],w[p],idx;//邻接表模板,新增一个w数组,表示这个边的权重
int d[p];//表示每个点距离起点的距离
bool st[p];//确定为最短路以及判断是否这个点是否是最小距离起点的点
int n,m;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;//邻接表模板
}
int dijkstra()
{
memset(d,0x3f,sizeof d);//将距离全都初始化为无穷大
d[1]=0;//第一个点1距离起点1为0
priority_queue<PII,vector<PII>,greater<PII>>heap;//优先队列,建立一个小根堆,为pair类型
//分别储存距离和是哪个点
heap.push({0,1});//第一个数表示距离起点的距离,第二个数表示某点
while(heap.size())//队列不为空,也是每次循环找一个最短距离存入st数组
{
PII t=heap.top();//定义一个pair类型的变量存队头元素
heap.pop();//存完之后将队头删掉
int ver=t.second,distance=t.first;//分别将队头的两个元素取出来
if(st[ver])//如果是最小距离,即被访问过跳过下面的操作
continue;
st[ver]=true;//没有访问过将这个点标记
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];//用j表示这个点
if(d[j]>distance+w[i])//如果这个点的距离不是最小距离可以更新的话,用上一个点距离更新这个点距离
{
d[j]=distance+w[i];
heap.push({d[j],j});//将这个最小距离存入队列
}
}
}
if(d[n]==0x3f3f3f3f) return -1;//如果到不了n号点则距离为无穷大
return d[n];//否则返回这个距离
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout<<dijkstra();
return 0;
}