算法提高之热浪

算法提高之热浪

• 核心思想：单源最短路 + 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;
    }