题目描述
给定一个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 复杂度为O(n^2)
,当n很大时,就需要优化了,可以使用优先队列priority_queue
,能够自动排序,出列的时候的数据就已经是有顺序的了,再将邻接矩阵改为邻接表存储,可以有效节省时间和空间
需要找到最小的距离的节点,所以入队的时候包含两个元素,dis和当前节点,所以用typedef pair<int, int> PII
,使用pair捆绑两个整型
使用priority_queue<PII,vector<PII>,greater<PII> > q;
定义一个PII型的从小到大的优先对列q
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N=150010;
int n,m;
int dis[N]; //记录当前点与第一个点之间的距离
int h[N];
int e[N];//邻边的另一个端点
int ne[N];//链表的下一个结点下标
int w[N];//邻边的长度
int idx=0;
int vis[N];
int dijkstra()
{
memset(dis,0x3f,sizeof(dis));//本题要求最小值,初始化为极大值
dis[0]=1;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,1});//距离为0,第1个点
while(q.size()){
PII temp=q.top();
q.pop();
int d=temp.second;
int distance=temp.first;
if(!vis[d]){
vis[d]=1;
for(int i=h[d];i!=-1;i=ne[i]){
int j=e[i];
if(dis[j]>distance+w[i]){
dis[j]=distance+w[i];
q.push({dis[j],j});
}
}
}
}
if(dis[n]==0x3f3f3f3f){//最终一个点到第一个点的距离无穷大,即不存在最短路径
return -1;
}
else{
return dis[n];//第n个点到第一个点之间的距离
}
}
int main()
{
cin >> n >> m;
memset(h,-1,sizeof(h));//初始化为无穷大
while(m--){
int x,y,z;
cin >> x >> y >> z;
w[idx] = z;
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
cout << dijkstra() << endl;
return 0;
}