64分求助

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

__owowow__ @ 2024-09-04 12:08:57

我用 Dijkstra 算法来做这道题(加过队列优化的),但是只有 64 分,求大佬指点

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200005
struct node{
    int v,w;
};
struct dij{
    int dis,id;
};
bool operator <(const dij &x,const dij &y){
    return x.dis<y.dis;
}
vector<node> edge[MAXN];
int n,m,dis[MAXN],s,u,v,w;
priority_queue<dij> heap;
void Dijkstra(int s) {
    fill(dis+1,dis+n+1,INT_MAX);
    dis[s]=0;
    heap.push(dij{0,s});
    while(!heap.empty()) {
        dij cur=heap.top();
        heap.pop();
        int u=cur.id;
        if(cur.dis>dis[u]) continue;
        for(auto v:edge[u]) {
            if(dis[v.v]>dis[u]+v.w) {
                dis[v.v]=dis[u]+v.w;
                heap.push(dij{dis[v.v],v.v});
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        node t;
        t.v=v;
        t.w=w;
        edge[u].push_back(t);
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++) {
        cout<<dis[i]<<" ";
    }
    return 0;
}

by lao_wang @ 2024-09-04 12:18:11

@owowow 建议看看你的重载运算符,将 x.dis<y.dis 改成 x.dis>y.dis


by __owowow__ @ 2024-09-04 12:52:08

@lao_wang AC 了,但为什么?我本来是 TLE 。。。。能解释一下吗?


by lao_wang @ 2024-09-04 12:53:52

@owowow 首先重载运算符错了,其次因为没有标记为已有最短路到该节点,所以变成 SPFA


by __owowow__ @ 2024-09-21 08:00:01

@lao_wang 那请问怎么改这段程序才不是 SPFA 呢?


by lao_wang @ 2024-09-21 16:50:38

@owowow 您这不AC了吗


by lao_wang @ 2024-09-21 16:51:44

“其次因为没有标记为已有最短路到该节点”重新看了一下,没有这个问题,只有重载运算符的问题


|