dijkstra算法,示例能过,提交全错,求助!

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

jdv23442 @ 2022-03-30 21:34:03

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

const int maxn = 100005,INF = 99999999;
int n,m,s;
struct node{
    int to,w;
};
vector<node> e[maxn];
int dis[maxn];
bool vis[maxn];

void dijkstra() {
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while(!q.empty()) {
        int p = q.front(); q.pop();
        cout<<"pop "<<p<<endl;
        int size = e[p].size();
        int minP = INF, minPos = 0; // 最小值,最小值对应的点 
        for(int i=0;i<size;i++) {
            int t = e[p][i].to;
            int w = e[p][i].w;
            dis[t] = min(dis[t],dis[p]+w);
            if(dis[t] < minP && !vis[t]) {
                minP = dis[t];
                minPos = t;
            }
        }
        if(minP != INF) {
            vis[minPos] = true;
            q.push(minPos);
        }
    }
}

int main(){
    cin>>n>>m>>s;
    int u,v,w;
    for(int i=1;i<=m;i++) {
        cin>>u>>v>>w;
        node p; p.to = v; p.w = w;
        e[u].push_back(p);
    }
    for(int i=1;i<=n;i++)
        dis[i] = INF;
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;
}

by LYqwq @ 2022-03-30 21:36:19

    queue<int> q;

大无语

建议重学


by jdv23442 @ 2022-03-30 21:47:03

@LYqwq 这有什么不行吗?


by LYqwq @ 2022-03-30 21:48:56

如果你懂 dij 的原理的话咋可能这么写,样例能过都是奇迹


by jdv23442 @ 2022-03-30 21:55:38

@LYqwq 感谢你的回复!我这也是第一次写dij,本来不会写,看题解的思路写的。感觉没什么问题啊!初始化源点距离为0,其他INF,每次选一个距离最小的点入队,遍历并更新它的出点的距离,再把最小的一个点加入队列,并标记访问,这没什么不对啊!


by jdv23442 @ 2022-03-30 21:57:50

看其他讨论后增加了边的去重,还是不行

    cin>>n>>m>>s;
    int u,v,w;
    for(int i=1;i<=m;i++) {
        cin>>u>>v>>w;
        int flag = true;
        for(int i=0;i<e[u].size();i++) {
            if(e[u][i].to == v) {
                flag = false;
                e[u][i].w = max(e[u][i].w,w);
            }
        }
        if(flag) e[u].push_back((node){v,w});
    }

by Sharpsmile @ 2022-03-30 21:58:33

@jdv23442 啊这这这,dij是在所有点之中选择最近的,不是只有这次更新过的啊。。。。。。


by junxis @ 2022-03-30 21:58:40

@jdv23442

DIJ怎么可能是用queue实现的啊?

要么set要么priority_queue啊。。。


by Sharpsmile @ 2022-03-30 21:59:09

所有指所有没有遍历过的节点


by jdv23442 @ 2022-03-30 22:00:50

确实是,确实是,原理还没搞懂就写了。。。 感谢大家!


|