算法提高之热浪

admin2024-05-15  0

算法提高之热浪

  • 核心思想:单源最短路 + 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;
      }
    
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!