求教,关于SPFA例程:存边和遍历没有看懂
查看原帖
求教,关于SPFA例程:存边和遍历没有看懂
465029
Specter_LiZN楼主2024/10/3 16:19

在addEdge函数(存边)中的两行(###标记的)没看懂,有人指出一下它们的作用吗?第37行也没看懂,谢谢dalao!

#include <bits/stdc++.h>
#define f(i,a,b) for(int i=a;i<=b;i++)
#define m(i,a,b) for(int i=a;i>=b;i--)
#define ArrayOut(a,b,outArray,beg,wid) f(i,beg,a){f(j,beg,b)cout<<setw(wid)<<outArray[i][j];cout<<'\n';}
#define Shion cout <<'\n'<<"Shion is too poor to print that."
const signed Miku=0x3f3f3f3f;
const signed N=1e4+50,M=500050;
using namespace std;
int n,m,s,edgeCnt=0;
int dis[N],vis[N],head[M];
struct Edge{
  int next,to,dis;
}edge[M]; //静态邻接表

void addEdge(int from,int to,int dis){
  edgeCnt++;//边数
  edge[edgeCnt].next=head[from]; //链式存储下一条出边###问题在此
  edge[edgeCnt].to=to; //当前节点编号
  edge[edgeCnt].dis=dis; //本条边的距离
  head[from]=edgeCnt; //记录下一次的出边情况###问题在此
}
void spfa()
{
  queue<int> q; //spfa用队列
  f(i,1,n){
    dis[i]=Miku; //带权图初始化
    // vis[i]=0; //记录点i是否在队列中
  }
  q.push(s); dis[s]=0; vis[s]=1; //第一个顶点入队,进行标记
  while(!q.empty())
  {
    int u=q.front(); //取出队首
    q.pop(); vis[u]=0; //出队标记
    for(int i=head[u]; i; i=edge[i].next) //邻接表遍历,可用vector代替//在循环结束后i变为next
    {
      int v=edge[i].to; 
      if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
      {
        dis[v]=dis[u]+edge[i].dis;
        if(vis[v]==0) //未入队则入队
        {
          vis[v]=1; //标记入队
          q.push(v);
        }
      }
    }
  }
}
signed main(){
  ios::sync_with_stdio(0),cin.tie(0);
  cin>>n>>m>>s;
  for(int i=1; i<=m; i++)
  {
    int f,g,w;
    cin>>f>>g>>w; 
    addEdge(f,g,w); //建图:有向图连一次边
  }
  spfa();
  f(i,1,n)
    // if(s==i)
    //   cout<<0<<" "; //如果是回到自己,直接输出0
    // else
      cout<<dis[i]<<" "; //否则打印最短距离
  return 0;
  Shion;
}

2024/10/3 16:19
加载中...