问一下这段代码的性质

P4779 【模板】单源最短路径(标准版)

_TLEer_的小号 @ 2022-07-20 08:59:18

rt.

手打了一遍,发现自己写的像优先队列优化的spfa.

所以这段到底是spfa还是dijkstra?

code在二楼。


by _TLEer_的小号 @ 2022-07-20 08:59:41

#include<bits/stdc++.h>
#define il inline
#define re register
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
struct ln{
    int u,v,w,nxt;
}a[400010];
struct fk{
    int a;
    fk(int b){a=b;}
    fk(){}
};
int dij[100010],lnsz,hd[100010],n,m,u,v,w,sor;
bool goed[100010];
void mrg(int u,int v,int w){
    a[++lnsz].u=u;
    a[lnsz].v=v;
    a[lnsz].w=w;
    a[lnsz].nxt=hd[u];
    hd[u]=lnsz;
}
const bool operator< (const fk a,const fk b) {
    return dij[a.a]>dij[b.a];
}
priority_queue<fk> q;
void dijkstra(int root){
    q.push(fk(root));
    dij[root]=0;
    while(!q.empty()){
        int tp=q.top().a;
        q.pop();
        goed[tp]=false;
        for(int i=hd[tp];i;i=a[i].nxt)
            if(dij[tp]+a[i].w<dij[a[i].v]){
                dij[a[i].v]=dij[tp]+a[i].w;
                if(!goed[a[i].v]){
                    q.push(fk(a[i].v));
                    goed[a[i].v]=true;
                }
            }
    }
}
signed main(){
    cin>>n>>m>>sor;
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        mrg(u,v,w);
    }
    for(int i=0;i<=n;i++)dij[i]=INF;
    dijkstra(sor);
    for(int i=1;i<=n;i++)
        cout<<dij[i]<<' ';
    cout<<endl;
    return 0;
}

by Sharing666 @ 2022-07-20 09:02:46

感觉像优化的 \text{dijkstra}


by zesqwq @ 2022-07-20 09:03:43

@_TLEer_的小号 感觉是复杂度不正确的最差nmlogm 的SPFA


by _TLEer_的小号 @ 2022-07-20 09:04:57

@Sharing666 但是dijkstra的vis(代码中的goed)是不用重新赋值false的吧(


by _TLEer_的小号 @ 2022-07-20 09:06:43

@zhouershan 那要怎么改成dijkstra啊(


by fjy666 @ 2022-07-20 09:09:10

SPFstra


|