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
以下是我的观点:
std::priority_queue
假掉了,相当于 std::queue
,因为 std::priority_queue
基于堆实现。@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。