spfa算法(用于求有负权边的题 以及求负环)
/*
与堆优化版的dij差别就是 堆优化版的每次用当前最短的去更新下一个,并且每个点只能用于更新一次
而spfa用与处理负权边(这次最短的边更新的点不一定比比它长的边更新的其他点距离短)
所以spfa不用 优先队列 只用普通队列 只要每次更新成功 就加入该点
用于重新更新该点能到的所有点 队列中的点不能重复
因为重复没有意义(只有更新了才能加入而如果队列里有那就直接用之前放进去的那个就行了)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
vector<PII> u[N];
int dist[N];
bool st[N];
int n,m;
void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
st[1]=1;
while(q.size())
{
int t=q.front();
q.pop();
st[t]=0;
int len=u[t].size();
for(int i=0;i<len;i++)
{
int id=u[t][i].first;
int dd=u[t][i].second;
if(dist[t]+dd<dist[id])
{
if(!st[id])
{
q.push(id);
st[id]=1;
}
dist[id]=dist[t]+dd;
}
}
}
if(dist[n]==0x3f3f3f3f) puts("impossible");
else cout<<dist[n];
}
int main()
{
cin>>n>>m;
while (m -- )
{
int x,y,z;
cin>>x>>y>>z;
u[x].push_back({y,z});
}
spfa();
}