狄克斯特拉算法问题

柿子饼同学

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. #define inf 999999999
   
4. 
   
5. int n, m, s;
   
6. int mp[1002][1002]; // mp[x][y] : x -> y 邻接矩阵存有向图 , [x][y] 代表 x - > y
   
7. int start;
   
8. int dist[1002]; // start -> dist[v] 最短路径 start 到 dist v 的最短路
   
9. int pre[1002]; // prenode[v] -> v 就是v的前驱节点
   
10. bool isused[1002];
    
11. 
    
12. void Dijkstra(int start){
    
13.     fill(dist, dist+1002, inf); // 初始化
    
14.     for(int i = 1; i < n; i++){
    
15.         if(mp[start][i]) dist[i] = mp[start][i]; // 与开始节点的连线 , 不然就是 inf
    
16.     }
    
17.     dist[start] = 0;
    
18.     isused[start] = 1;
    
19.     pre[start] = 0; // INIT 初始化
    
20. 
    
21.     for(int i = 1; i <= n; i++){
    
22.         int mindist = inf;
    
23.         int u = start;
    
24.         for(int j = 1; j <= n; j++){ // 找到与 开始节点 联通且边权最小的节点 u
    
25.             if(!isused[j] && dist[j] < mindist){
    
26.                 mindist = dist[j];
    
27.                 u = j;
    
28.             }
    
29.         }
    
30.         isused[u] = 1; // u 用过了
    
31.         for(int j = 1; j <= n; j++){ // 找到与 u 相邻且权值最小的节点
    
32.             if(!isused[j] && mp[u][j] != 0){
    
33.                 int newdist = mp[u][j] + dist[u]; // 更新 dist
    
34.                 if(newdist < dist[j]){
    
35.                     dist[j] = newdist;
    
36.                     pre[j] = u;
    
37.                 }
    
38.             }
    
39.         }
    
40.     }
    
41. }
    
42. 
    
43. int main(){
    
44.     ios::sync_with_stdio(0);
    
45.     memset(mp, 0, sizeof(mp));
    
46.     cin >> n >> m >> s;
    
47. 
    
48.     for(int i = 0; i < m; i++){
    
49.         int u, v, w;
    
50.         cin >> u >> v >> w;
    
51.         mp[u][v] = w;
    
52.     }
    
53. 
    
54.     Dijkstra(s);
    
55. 
    
56.     for(int i = 1; i <= n; i++){
    
57.         cout << dist[i] << ' ';
    
58.     }
    
59. 
    
60.     return 0;
    
61. }

复制代码

测试用例 2 :

1. 5 15 5
   
2. 2 5 181
   
3. 1 5 98
   
4. 4 2 49
   
5. 3 2 262
   
6. 4 3 26
   
7. 2 4 192
   
8. 5 1 221
   
9. 2 2 254
   
10. 4 4 233
    
11. 1 5 44
    
12. 5 4 67
    
13. 4 2 214
    
14. 1 1 47
    
15. 1 1 118
    
16. 5 4 3
    

复制代码

正确输出 :

1. 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
可能是故意的吧

哈哈哈