dj咋能写成spfa的效果???
2026-10-28 18:22:37
发布于:广东
额,就是呢,大家众所周知,单源最短路2的代码正解是spfa,而我却用dj加spfa的特判能过???
代码








#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e3+10;
ll n,m,s,cnt,head[N],d[N],dd[N];
ll mx=(1<<31)-1;
struct lsqxx{
int v,w,nxt;
}l[2*N];
void add(int u,int v,int w){
cnt++;
l[cnt].v=v;
l[cnt].w=w;
l[cnt].nxt=head[u];
head[u]=cnt;
}
void dj(ll s){
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;
q.push({0,s});d[s]=0;
while(q.size()){
pair<ll,ll>p=q.top();q.pop();
ll u=p.second,di=p.first;
if(di!=d[u])continue;
dd[u]++;
if(dd[u]>=n){
cout<<"no solution";
exit(0);
}
for(int i=head[u];i!=0;i=l[i].nxt){
ll v=l[i].v,w=l[i].w;
if(d[v]>di+w){
d[v]=di+w;
q.push({d[v],v});
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
for(int i=1;i<=n;i++)d[i]=mx;dj(s);
for(int i=1;i<=n;i++){
if(d[i]==mx)cout<<-1<<" ";
else cout<<d[i]<<" ";
}
return 0;
}
哪位大佬告诉我是为什么???
全部评论 1
注:gpt说这是dj模板
1周前 来自 广东
0




















有帮助,赞一个