求助,愣是没发现哪里错

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

码迷元首 @ 2022-09-19 19:08:08

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

}

by 码迷元首 @ 2022-09-19 19:12:51

哦哦,把w<b.w改成w>b.w就a了


|