萌新刚学Dij板子求调,WA52pts只对点2,5,6

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

Greenzhe @ 2022-09-03 09:10:54

建的是有向边,数组也没有开小,求问各位大佬哪里写挂了

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

int n,m,s;
int dis[100005];
bool vis[100005];
struct edge{
    int v,w; //v终点,w权值
};
vector<edge> rel[100005]; 
const int INF=0x3f3f3f3f;

void dijkstra();

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);
        rel[u].push_back({v,w});
    }
    memset(dis,0x3f,sizeof(dis));
    dijkstra();
    for(int i=1;i<=n;++i)
        printf("%d ",dis[i]);
    printf("\n");
    return 0;
}
struct cmp{
    bool operator()(int a,int b){
        return dis[a]>dis[b];
    }
}; //自定义比较仿函数,用于小根堆
void dijkstra(){
    priority_queue<int,vector<int>,cmp> q;
    dis[s]=0;
    vis[s]=true;
    q.push(s);
    while(!q.empty()){
        int x=q.top();
        q.pop();
        for(int i=0;i<rel[x].size();++i){
            int y=rel[x][i].v;
            if(dis[x]+rel[x][i].w<dis[y]){
                dis[y]=dis[x]+rel[x][i].w;
                if(!vis[y]){
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
    }
}

by yinhee @ 2022-09-03 09:35:22

@蒟蒻·廖子阳 这就是spfa吧……


by lzyqwq @ 2022-09-03 09:36:08

@yinhee 但是他用了优先队列


by lzyqwq @ 2022-09-03 09:36:35

@yinhee 不就比spfa更假了吗(


by Seal_l @ 2022-09-03 09:38:19

sptra!


by Greenzhe @ 2022-09-03 09:38:37

玄学(雾


by FiraCode @ 2022-09-03 09:38:51

@Seal_l woc!


by yinhee @ 2022-09-03 09:39:20

@蒟蒻·廖子阳 dijkspfa(雾


by Greenzhe @ 2022-09-03 09:40:49

我去loj上测测


by Greenzhe @ 2022-09-03 09:42:40

loj上也过了(


by Greenzhe @ 2022-09-03 09:44:54

那么好吧,此贴先结了

@蒟蒻·廖子阳 @李佳和 @FiraCode @yinhee @Seal_l

谢谢大佬


上一页 | 下一页