题目
给定一个 n个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1号点到 n 号点的最短距离，如果无法从 1 号点走到 n号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m行每行包含三个整数 𝑥,𝑦,𝑧，表示存在一条从点 𝑥 到点 𝑦 的有向边，边长为 𝑧。
输出格式
输出一个整数，表示 1号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×10^5,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 10^9。
输入样例
3 3
1 2 2
2 3 1
1 3 4
输出样例
3分析题目
在此题中，可能存在自环，重边，在Dijkstra中不需要考虑重边自环，算法本身就已经处理好了，
Dijkstra算法是针对所有边权均为非负值的，那么我们可以根据题目所给出的信息判断此题使用的
是Dijkstra算法，在Dijkstra算法中，又分为朴素版和堆优化版，可以根据所给的数据以及时间复杂
度来判断，当n与m的数值几乎一致时或者说时间复杂度是O（mlogn+n）,则使用堆优化版，当n与
m相差几千至几万倍时或者说时间复杂度为O（n^2+m）,则使用朴素版。
时间复杂度
1、d[1] = 0,d[i] = 0x3f;
2、for :i:1~n;
t不在S中的距离最近的点 O（1）n次
S<---t遍历 n次
用t更新其他点的距离 m次logn
时间复杂度是 O(mlogn+n)
题目代码
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
const int N = 1.5e5+10;//数据加强1.5*10^5
using namespace std;
typedef pair<int,int> PLL;
int n,m;
int e[N],h[N],ne[N],w[N],idx;//w是权重,也就是a到b的距离
int d[N];//计算距离
bool st[N];//是否记录
void add(int a,int b,int c)//a和b用链表表示
{
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int dijkstrea()
{
memset(d,0x3f,sizeof d);//初始化
d[1] = 0;//第一个点的距离为0
priority_queue<PLL,vector<PLL>,greater<PLL>>head;//优先队列，小根堆
head.push({0,1});//把第一个点添加到队列中
while(!head.empty())
{
auto t = head.top();//返回最高优先级元素
head.pop();//出队
int ver = t.second,ds= t.first;//ver表示b点，distance表示a点到b点的距离
if(st[ver])continue;//表示该点已经计算过了
st[ver] =true;
for(int i = h[ver];i!=-1;i = ne[i]) //遍历所有点的所有边
{
int j = e[i];
if(d[j]>ds+w[i])
{
d[j] = ds+w[i];
head.push({d[j],j});
}
}
}
if(d[n] == 0x3f3f3f3f)return -1;
return d[n];
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
printf("%d",dijkstrea());
return 0;
}欢迎大佬们来指点，嘻嘻
