Dijkstra堆优化TLE 64pts 悬关求调

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

program_xwl @ 2024-08-27 16:39:27

代码:

#include <bits/stdc++.h>
using namespace std;

struct road {long long v,w;};
struct node
{
    long long x,sum;
    bool operator<(const node &b)const {return sum < b.sum;}
};
long long n,m,st,dis[100005];
vector<road>g[100005];
priority_queue<node>pq;

void dij(long long st)
{
    memset(dis,0x3f,sizeof(dis));
    while(pq.size()) pq.pop();
    dis[st] = 0;
    pq.push({st,0});
    while(!pq.empty())
    {
        node u = pq.top();
        pq.pop();
        if(dis[u.x] < u.sum) continue;
        for(long long i = 0;i < g[u.x].size();i++)
        {
            long long nx = g[u.x][i].v,w = g[u.x][i].w;
            if(dis[nx] > u.sum+w)
            {
                dis[nx] = u.sum+w;
                pq.push({nx,u.sum+w});
            }
        }
    }
    return;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> st;
    for(long long i = 1;i <= m;i++)
    {
        long long u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    dij(st);
    for(long long i = 1;i <= n;i++) cout << dis[i] << ' ';
    return 0;
}

by lzm0107 @ 2024-08-27 16:41:46

@program_xwl

bool operator<(const node &b)const {return sum < b.sum;}

改成

bool operator<(const node &b)const {return sum > b.sum;}


by program_xwl @ 2024-08-27 16:55:44

@lzm0107 感谢,已 AC ,已关


|