$$\Huge\color{blue}{spfa求最短路}$$
作者:
incra
,
2022-05-14 06:25:54
,
所有人可见
,
阅读 225
<-录制视频不容易,点个赞再走呗
代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010,M = 100010,INF = 0x3f3f3f3f;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
bool st[N];
void add (int a,int b,int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa () {
memset (dist,0x3f,sizeof (dist));
dist[1] = 0;
queue <int> q;
q.push (1);
while (!q.empty ()) {
int t = q.front ();
q.pop ();
st[t] = false;
for (int i = h[t];~i;i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t]+w[i]) {
dist[j] = dist[t]+w[i];
if (!st[j]) {
q.push (j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main () {
memset (h,-1,sizeof (h));
cin >> n >> m;
while (m--) {
int a,b,c;
cin >> a >> b >> c;
add (a,b,c);
}
int ans = spfa ();
if (ans == INF) puts ("impossible");
else cout << ans << endl;
return 0;
}
习题