spfa笔记
作者:
陈.6.29
,
2023-11-07 22:07:55
,
所有人可见
,
阅读 94
include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int, int> PII;//堆里存储距离和节点编号
const int N = 1e6 + 10;
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 spfa(){
memset(dist,0x7f,sizeof dist);
dist[1]=0;//初始化
queue<int> q; // 建立队列
q.push(1); // 把第一个开始的点放入
st[1]=1;//表示队列里有1了
while(q.size()){ // 判断是否把所有点都遍历了
int t=q.front();//去除队列中的第一个点
// cout << t.x << " " << t.y << endl;
q.pop(); //把这个点删除
st[t]=0;//这个点已经不在du
for(int i=h[t];i!=-1;i=ne[i]){//遍历所有的边
int j=e[i];//取指向下一个点的值
if(dist[j]>dist[t]+w[i]){//毕较长度
dist[j]=dist[t]+w[i];
if(st[j]==0) q.push(j),st[j]=1;//插入
}
}
}
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的边
add(b,a,c);//无向边情况
}
spfa();
return 0;
}