68pts WA 求调 orz

RainbowSheep_ @ 2024-08-29 19:19:16

//https://www.luogu.com.cn/problem/P4779
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <bitset>
using namespace std;

#define MAXN 100010

struct edge
{
    int to,w;
};

vector<edge> graph[MAXN];
bitset<MAXN> vis;
int dis[MAXN],n,m,s,ui,vi,wi,u;

struct lowest
{
    bool operator()(const int a,const int b)
    {
        return dis[a]>dis[b];
    }
};

priority_queue<int,vector<int>,lowest> pq;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++)
    {
        cin >> ui >> vi >> wi;
        graph[ui].push_back({vi,wi});
    }
    for(int i=1;i<=n;i++)
        dis[i]=INT_MAX;
    dis[s]=0;
    pq.push(s);
    while(!pq.empty())
    {
        u=pq.top();
        pq.pop();
        if(vis[u])
            continue;
        for(int i = 0;i<graph[u].size();i++)
        {
            if(dis[graph[u][i].to]>dis[u]+graph[u][i].w)
            {
                dis[graph[u][i].to]=dis[u]+graph[u][i].w;
                pq.push(graph[u][i].to);
            }
        }
        vis[u]=true;
    }
    for(int i=1;i<=n;i++)
        cout << dis[i] << " ";
    cout << endl;
    return 0;
}

by _std_O2 @ 2024-08-29 19:49:00

堆里应该维护两个变量，一个是距离，一个是点的编号。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int ans[N],s,n,m;
bool vis[N];
struct edge{
    int v,w;
    //一条从u->v,边权为w的边
};
vector<edge>g[N];
struct node{
    int p,w;//p为点的编号，w为边权
    bool operator<(const node& b)const&{
        return b.w<w;
    }
};
priority_queue<node> q;
void dij(){
    q.push({s,0});
    ans[s]=0;
    while(!q.empty()){
        node now=q.top();
    //  cout<<now.p<<" ";
        q.pop();
        if(vis[now.p]==1) continue;
        vis[now.p]=1;
        int len=g[now.p].size();
        for(int i=0;i<len;i++){
            int gv=g[now.p][i].v;
            int gw=g[now.p][i].w;
            if(ans[now.p]+gw<ans[gv]){
                ans[gv]=ans[now.p]+gw;
                q.push({gv,ans[gv]});
            }
        }
    }
}
int main(){
    memset(ans,0x3f,sizeof(ans));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
    }
    dij();
//  cout<<endl;
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}

@RainbowSheep_

by yuanshuu @ 2024-09-11 19:34:57

@RainbowSheep_ 哈哈哈，我也是这个错误

原因就是你自定义的cmp中dis[a] 与dis[b]是变化的 会导致紊乱

by RainbowSheep_ @ 2024-09-15 12:16:28

@yuanshuu 有道理