算法提高之热浪
核心思想:单源最短路 + spfa
- spfa:如果该点没有在队列中 加入队列 用其更新与其他点距离
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int M = 6210 * 2 , N = 2510; int h[N],ne[M],e[M],w[M],idx; int dist[N],q[N]; bool st[N]; int n,m,S,T; void add(int a,int b,int c) { e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++; } void spfa() { memset(dist,0x3f,sizeof dist); int hh=0,tt=1; dist[S] = 0; q[0] = S; st[S] = true; while(hh!=tt) { int t = q[hh++]; st[t] = false; if(hh == N) hh=0; 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[tt ++ ] = j; if (tt == N) tt = 0; st[j] = true; } } } } } int main() { cin>>n>>m>>S>>T; memset(h, -1, sizeof h); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b, a, c); } spfa(); cout<<dist[T]<<endl; }