dijkstra笔记
作者:
陈.6.29
,
2023-11-07 22:06:48
,
所有人可见
,
阅读 79
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<int,int>p;
int n,m;//节点数量和边数
int h[N];//头节点
int e[N];//下一个的地址的值
int w[N];//边的长度
int ne[N];//下一个的地址
int idx;//模拟的地址
int dist[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++;//死背
}
void dijkstra(){
memset(dist,0x7f,sizeof dist);
dist[1]=0;
priority_queue<p,vector<p>,greater<p>> q;//小根堆,安装插进去的值自动排序,小的在上
//建立队列
q.push({dist[1],1});//把第一个开始的点放入
while(q.size()){//判断是否把所有点都遍历
auto t=q.top();
int td=t.first,dian=t.second;
q.pop();//把这个点删除
if(st[dian]==1) continue;
st[dian]=1;
for(int i=h[dian];i!=-1;i=ne[i])//遍历所有的边
{int j=e[i];//取指向下一个点的值
if(dist[j]>dist[dian]+w[i]){//比较长度
dist[j]=dist[dian]+w[i];
q.push({dist[j],j});
}
}
}
if(dist[n]>=0x7f7f7f7f){
cout<<-1<<endl;
return ;
}
else cout<<dist[n];
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);//加一条a指向b距离的c的边
}
dijkstra();
return 0;
}