柿子饼同学 发表于 2022-7-4 22:55:03

狄克斯特拉算法问题

本帖最后由 柿子饼同学 于 2022-7-4 23:03 编辑

题目在下, 代码 :
https://www.luogu.com.cn/problem/P3371
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999

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

void Dijkstra(int start){
    fill(dist, dist+1002, inf); // 初始化
    for(int i = 1; i < n; i++){
      if(mp) dist = mp; // 与开始节点的连线 , 不然就是 inf
    }
    dist = 0;
    isused = 1;
    pre = 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 && dist < mindist){
                mindist = dist;
                u = j;
            }
      }
      isused = 1; // u 用过了
      for(int j = 1; j <= n; j++){ // 找到与 u 相邻且权值最小的节点
            if(!isused && mp != 0){
                int newdist = mp + dist; // 更新 dist
                if(newdist < dist){
                  dist = newdist;
                  pre = 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 = w;
    }

    Dijkstra(s);

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

    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

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

柿子饼同学 发表于 2022-7-4 22:56:19

{:10_266:}

傻眼貓咪 发表于 2022-7-5 10:09:49

请问你的测试用例 2 数据正确吗？{:10_249:}

柿子饼同学 发表于 2022-7-5 10:30:31

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

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

柿子饼同学 发表于 2022-7-5 10:41:19

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

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

傻眼貓咪 发表于 2022-7-5 10:55:30

本帖最后由 傻眼貓咪 于 2022-7-5 10:56 编辑

柿子饼同学 发表于 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 11:02:12

柿子饼同学 发表于 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 11:06:50

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

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

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

柿子饼同学 发表于 2022-7-5 12:12:03

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

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

傻眼貓咪 发表于 2022-7-5 13:10:37

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

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

柿子饼同学 发表于 2022-7-5 17:31:00

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

可能是故意的吧{:10_277:}

傻眼貓咪 发表于 2022-7-5 17:49:28

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

哈哈哈{:10_254:}
页: [1]
查看完整版本: 狄克斯特拉算法问题