求助,孩子WA飞了

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

MornHus @ 2023-01-07 22:37:34

样例过了,但是16pts。 用的dijkstra+堆优化 可能存图方法有点奇怪:

#include<bits/stdc++.h>
#define maxn 100001
#define maxm 200001
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,u,v,w;
struct node{
    int to,val;
};
bool vis[maxn];
vector<node>gragh[maxn];
int dis[maxn];
struct point{
    int id,distance;
    bool operator < (const point &a)const{
        return distance<a.distance; 
    } 
};
priority_queue<point>q;
inline void dijkstra(){
    for(int i=1;i<=n;i++){
        if(i==s)continue;
        dis[i]=inf;
    }
    q.push({s,0});
    while(!q.empty()){
        point curr=q.top();q.pop();
        if(vis[curr.id])continue;
        vis[curr.id]=1;
        for(int i=0;i<gragh[curr.id].size();i++){
            if(dis[gragh[curr.id][i].to]>dis[curr.id]+gragh[curr.id][i].val){
                dis[gragh[curr.id][i].to]=dis[curr.id]+gragh[curr.id][i].val;
                q.push({gragh[curr.id][i].to,dis[gragh[curr.id][i].to]});
            }
        }
    }
}
int main(){
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        gragh[u].push_back({v,w});
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}


by Usada_Pekora @ 2023-01-07 22:57:04

@MornHus 默认大根堆。


by MornHus @ 2023-01-07 23:02:19

@Zyingyzzz 该怎样改呢?


by MornHus @ 2023-01-07 23:02:58

@Zyingyzzz 我把重载运算符的小于改成大于会CE


by Usada_Pekora @ 2023-01-07 23:04:28

@MornHus 你不能改里面那个?


by Ruiqun2009 @ 2023-01-07 23:04:42

@MornHus 这样:

struct point{
    int id,distance;
    bool operator < (const point &a)const{
        return distance>a.distance; 
    } 
};

by HeCao2008 @ 2023-01-07 23:05:24

@MornHus 我建立小根堆的办法:

priority_queue<int , vector<int> , greater <int> > q;

by Ruiqun2009 @ 2023-01-07 23:06:02

@HeCao2008 但你这样没有适配 point


by MornHus @ 2023-01-07 23:06:06

@Zyingyzzz 谢谢,已经AC!


by HeCao2008 @ 2023-01-07 23:09:44

@Ruiqun2009 从别的地方复制过来的(


by HeCao2008 @ 2023-01-07 23:10:26

@Ruiqun2009 哦不对我是小丑,这道题要重载运算符


| 下一页