这个假得离谱的玩意为什么能过

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

atarashiTLE @ 2023-10-17 17:28:42

如题。主要错误点:修改了堆中点优先级相对值,dijkspfa。

#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 vis[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;
}
struct cmp{
    bool operator () (int a,int b){
        return dij[a]>dij[b];
    }
};
priority_queue<int,vector<int>,cmp> q;
void dijk(int root){
    dij[root]=0;vis[root]=1;
    q.push(root);
    while(!q.empty()){
        int tp=q.top();q.pop();vis[tp]=0;
        for(int i=hd[tp];i;i=a[i].nxt)
            if(dij[a[i].v]>dij[tp]+a[i].w){
                dij[a[i].v]=dij[tp]+a[i].w;
                if(!vis[a[i].v]){
                    vis[a[i].v]=1;
                    q.push(a[i].v);
                }
            }
    }
}
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;
    dijk(sor);
    for(int i=1;i<=n;i++)
        cout<<dij[i]<<' ';
    cout<<endl;
    return 0;
}

by _fairytale_ @ 2023-10-17 17:41:02

这个算法是正确的。

没太看懂你的问题,就按我的理解说吧。

首先是修改 dij 数组的值,priority_queue的排序是在你 push 进去之后就完成的,所以修改数组不会影响。

然后是 dijkspfa 的问题,在 dijkstra 算法中,每个点最多被更新一次,所以 vis 数组是无所谓的,因为它的作用只是判定一个点是否被更新过,至于更新之后是不是 0都可以。


by lovely_hyzhuo @ 2023-10-17 17:42:16

dijkspfa


by atarashiTLE @ 2023-10-17 18:11:16

@frostaur_ 感谢。


by ICE_Dice1024 @ 2023-10-17 19:15:23

以下是我的观点:

  1. 算法正确性没有问题。
  2. std::priority_queue 假掉了,相当于 std::queue,因为 std::priority_queue 基于堆实现。
  3. 时间复杂度貌似是错的,我不会卡。

@frostaur_

在 Dijkstra 算法中,每个点最多被更新一次,所以 vis 数组是无所谓的,因为它的作用只是判定一个点是否被更新过,至于更新之后是不是 0 都可以。

我觉得这句话不太对,貌似是因为一个点可能会被入队多次,如果不设置 vis 数组,一个节点可能会遍历很多次出边,然后导致时间复杂度没有保证。


by _fairytale_ @ 2023-10-17 19:49:19

@atarashiTLE 对不起。我确实想错了。

您的 vis 数组用错了,应该是出队的点 vis 设成 1。

@December456 谢谢指出。您的应该是对的。


by atarashiTLE @ 2023-10-17 19:59:33

@frostaur_ 非也。很多地方都错了。比如上面提到的堆中元素被修改问题。现在我的结论是这是一个带随机化的堆优化spfa,不知怎么被卡。


by _fairytale_ @ 2023-10-17 20:01:28

@atarashiTLE spfa 所谓的“堆优化”是假的,可以被卡到指数级。


by atarashiTLE @ 2023-10-17 20:02:35

@frostaur_ 这里带了随机化。具体原因:修改priority_queue中元素相对大小似乎是ub。


|