68pts WA 求调 orz
查看原帖
68pts WA 求调 orz
353264
RainbowSheep_楼主2024/8/29 19:19

新手初学Dijkstra,扩容数组并未AC,请问代码逻辑有什么问题吗

//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;
}
2024/8/29 19:19
加载中...