关于spfa的疑惑(60pts)
查看原帖
关于spfa的疑惑(60pts)
556656
虫二bug2楼主2024/8/27 11:34

这题如果不用拓扑排序,spfa可以优化过吗?

#include<bits/stdc++.h>
#define N 100001
using namespace std;
int n,m;
vector<int> E[N];
int dis[N];
void bfs(){
	int u=0;
	queue<int> q;
	q.push(u);
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(int v:E[u]){
			if(dis[u]+1>dis[v]){
				dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		E[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		E[0].push_back(i);
	}
	bfs();
	for(int i=1;i<=n;i++)cout<<dis[i]<<endl;
}
2024/8/27 11:34
加载中...