48分求助

Eureka_yzy @ 2022-09-18 10:51:16

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n,m,vis[N],dis[N],s;
struct edge{
    int to,w;
};
struct node{
    int u,w;
    bool operator < (const node x)const{
        return x.w<w;
    }
};
vector<edge> v[N];
priority_queue<node> q;
int main(){
    memset(dis,0x7f7f7f7f,sizeof(dis));
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int u,to,w;
        scanf("%d%d%d",&u,&to,&w);
        v[u].push_back((edge){to,w});
    }
    vis[s]=1;
    dis[s]=0;
    q.push((node){s,0});
    while(!q.empty()){
        int u=q.top().u,w=q.top().w;
        vis[u]=1;
        q.pop();
        for(int i=0;i<v[u].size();i++){
            int to=v[u][i].to;
            if(dis[u]+v[u][i].w<dis[to]){
                dis[to]=dis[u]+v[u][i].w;
                if(!vis[to]) q.push((node){to,dis[to]});
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
} 

by iiiiiyang @ 2022-09-18 10:57:29

@yaozhenyang 你这个是BF和dij掺杂体吧，为啥没有判断是否走过这个点呢

by iiiiiyang @ 2022-09-18 10:58:23

@yaozhenyang

int t=q.top().second; 
q.pop();
if(vis[t]) continue;
vis[t]=1;

大抵加这么一个if

by Eureka_yzy @ 2022-09-18 11:00:32

@forqprever 过了过了 属于是神经错乱了（）

by Eureka_yzy @ 2022-09-18 11:00:43

@forqprever 感谢

by Alone0213 @ 2022-09-18 11:04:06

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n,m,vis[N],dis[N],s;
struct edge{
    int to,w;
};
struct node{
    int u,w;
    bool operator < (const node x)const{
        return x.w<w;
    }
};
vector<edge> v[N];
priority_queue<node> q;
int main(){
    memset(dis,0x7f7f7f7f,sizeof(dis));
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int u,to,w;
        scanf("%d%d%d",&u,&to,&w);
        v[u].push_back((edge){to,w});
    }
    dis[s]=0;
    q.push((node){s,0});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        int siz=v[u].size();
        for(int i=0;i<siz;i++){
            int to=v[u][i].to;
            if(dis[u]+v[u][i].w<dis[to]){
                dis[to]=dis[u]+v[u][i].w;
                if(!vis[to]) q.push((node){to,dis[to]});
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}

by youyi2008 @ 2022-09-18 11:07:36

改成这样就行了

    dis[s]=0;
    q.push((node){s,0});
    while(!q.empty())
    {
        int u=q.top().u,w=q.top().w;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<v[u].size();i++)
        {
            int to=v[u][i].to;
            if(dis[u]+v[u][i].w<dis[to])
            {
                dis[to]=dis[u]+v[u][i].w;
                q.push((node){to,dis[to]});
            }
        }
    }

中间判重那里改到从堆顶获取节点时判断，加点时判断会导致很多重复计算