狄克斯特拉算法问题

柿子饼同学

题目在下, 代码 :
https://www.luogu.com.cn/problem/P3371

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

int n, m, s;
int mp[1002][1002]; // mp[x][y] : x -> y 邻接矩阵存有向图 , [x][y] 代表 x - > y
int start;
int dist[1002]; // start -> dist[v] 最短路径 start 到 dist v 的最短路
int pre[1002]; // prenode[v] -> v 就是v的前驱节点
bool isused[1002];

void Dijkstra(int start){
    fill(dist, dist+1002, inf); // 初始化
    for(int i = 1; i < n; i++){
        if(mp[start][i]) dist[i] = mp[start][i]; // 与开始节点的连线 , 不然就是 inf 
    }
    dist[start] = 0;
    isused[start] = 1;
    pre[start] = 0; // INIT 初始化

    for(int i = 1; i <= n; i++){
        int mindist = inf;
        int u = start;
        for(int j = 1; j <= n; j++){ // 找到与 开始节点 联通且边权最小的节点 u 
            if(!isused[j] && dist[j] < mindist){
                mindist = dist[j];
                u = j;
            }
        }
        isused[u] = 1; // u 用过了
        for(int j = 1; j <= n; j++){ // 找到与 u 相邻且权值最小的节点
            if(!isused[j] && mp[u][j] != 0){ 
                int newdist = mp[u][j] + dist[u]; // 更新 dist
                if(newdist < dist[j]){
                    dist[j] = newdist;
                    pre[j] = u;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    memset(mp, 0, sizeof(mp));
    cin >> n >> m >> s;

    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = w;
    }

    Dijkstra(s);

    for(int i = 1; i <= n; i++){
        cout << dist[i] << ' ';
    }

    return 0;
}

测试用例 2 :

5 15 5
2 5 181
1 5 98
4 2 49
3 2 262
4 3 26
2 4 192
5 1 221
2 2 254
4 4 233
1 5 44
5 4 67
4 2 214
1 1 47
1 1 118
5 4 3

正确输出 :

221 52 29 3 0 

但是我这个不能 , 不知道哪里有问题 , 求指出

柿子饼同学

傻眼貓咪

请问你的测试用例 2 数据正确吗？

柿子饼同学

傻眼貓咪 发表于 2022-7-5 10:09
请问你的测试用例 2 数据正确吗？

？
洛谷上的随机数据 ， 不知道欸

柿子饼同学

傻眼貓咪 发表于 2022-7-5 10:09
请问你的测试用例 2 数据正确吗？

难道我代码没问题?
题目里的样例是过了的

傻眼貓咪

柿子饼同学 发表于 2022-7-5 10:41
难道我代码没问题?
题目里的样例是过了的

测试用例 2
第 14 行：1 1 47
第 15 行：1 1 118
u -> v 如果 u = v 那么长度不是应该是 0 吗？

第 4 行：4 2 49
第 13 行：4 2 214
为什么可以重复 u -> v 但长度不同？

傻眼貓咪

柿子饼同学 发表于 2022-7-5 10:41
难道我代码没问题?
题目里的样例是过了的

正确答案：221 52 29 3 0
你的代码：221 217 29 3 0
如果不用代码计算，画在纸上计算，可以得知答案确实是 52
正确答案：5 -> 4 -> 2 = 3 + 49 = 52（最小）
你的代码：5 -> 4 -> 2 = 3 + 214 = 217
明显路径相同，但长度不一样（这和测试用例数据有关，因为重复路径）

傻眼貓咪

柿子饼同学 发表于 2022-7-5 10:41
难道我代码没问题?
题目里的样例是过了的

你的代码已经很完善了，只是没有考虑到重复路线选择其中最优路径问题，比如：
4 -> 2 有两条：
（一）4 2 49
（二）4 2 214

明显该选择路线一吧，但你的代码好象是以 FILO（先进后出）方式进行，所以选择了路线二。

柿子饼同学

傻眼貓咪 发表于 2022-7-5 11:06
你的代码已经很完善了，只是没有考虑到重复路线选择其中最优路径问题，比如：
4 -> 2 有两条：
（一）4 ...

？？？？？
这玩意还可以不止一条边？

傻眼貓咪

柿子饼同学 发表于 2022-7-5 12:12
？？？？？
这玩意还可以不止一条边？

不知道，因为测试用例是你发的，所以我才问，数据是否正确？

柿子饼同学

傻眼貓咪 发表于 2022-7-5 13:10
不知道，因为测试用例是你发的，所以我才问，数据是否正确？

可能是故意的吧

傻眼貓咪

柿子饼同学 发表于 2022-7-5 17:31
可能是故意的吧

哈哈哈