AcWing 851. spfa求最短路
原题链接
简单
作者:
憨包猫
,
2022-04-21 21:00:14
,
所有人可见
,
阅读 140
算法1
C++ 代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N],e[N],ne[N],w[N],idx;
int n,m,d[N],st[N];//st标记该点是否在队列里面
void add(int a,int b,int c)
{
w[idx] = c,e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void spfa()
{
queue<int> q;//用来存每一个d变小的点,再用该点去更新其他点
memset(d,0x3f,sizeof d);
q.push(1);
d[1] = 0;
st[1] = 1;
while (q.size())
{
int t = q.front();//每次取出队头
q.pop();
st[t] = 0;//取消标记,后面还可能再次更新
for (int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
if (d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];//不管该点是否在队列中,都要更新其距离
if (!st[j])//当距离变小且该点不在队列里面时,将该点加入队列
{
q.push(j);
st[j] = 1;
}
}
}
}
}
int main()
{
cin >> n >>m;
memset (h,-1,sizeof h);
while (m--)
{
int a,b,w;
cin >> a >> b >> w;
add(a,b,w);
}
spfa();
if (d[n] > 0x3f3f3f3f/2)puts("impossible");
else printf ("%d",d[n]);
return 0;
}