一道图的最短路径问题，大佬帮忙看下

798236606

题目：https://pintia.cn/problem-sets/9 ... /994805523835109376

之前用迪杰斯特拉算法和BF算法成功通过，但是BF算法的优化算法SPFA算法总是有两个点没通过。
看了一下午了，不知道哪里有问题

C++代码：

1. #include <cstdio>
   
2. #include <climits>
   
3. #include <cstring>
   
4. #include <vector>
   
5. #include <queue>
   
6. #include <set>
   
7. #include <algorithm>
   
8. 
   
9. using namespace std;
   
10. 
    
11. const int maxn = 510;
    
12. 
    
13. typedef struct node{
    
14.     int id, dis;
    
15. 
    
16.     node (int _id, int _dis) : id(_id), dis(_dis) {};
    
17. }Node;
    
18. 
    
19. int n, m, c1, c2;
    
20. int weight[maxn];//存放点权，即救援队数
    
21. int num[maxn];//存放到每个点的最短路径数
    
22. int w[maxn];//存放可聚集的队伍数
    
23. int d[maxn];//存放最短路径长度
    
24. bool inq[maxn];//是否在队列内
    
25. vector<Node> adj[maxn];//邻接表
    
26. set<int> pre[maxn];//存放顶点在最短路径中的前驱
    
27. 
    
28. void SPFA(int s)
    
29. {
    
30.     fill(d, d + n, INT_MAX);
    
31.     memset(w, 0, sizeof(w));
    
32.     memset(num, 0, sizeof(num));
    
33.     memset(inq, false, sizeof(inq));
    
34. 
    
35.     queue<int> q;
    
36.     q.push(s);
    
37.     w[s] = weight[s];
    
38.     d[s] = 0;
    
39.     num[s] = 1;
    
40.     inq[s] = true;
    
41. 
    
42.     while (!q.empty())
    
43.     {
    
44.         int u = q.front();
    
45.         q.pop();
    
46.         inq[u] = false;
    
47. 
    
48.         for (int v = 0; v < adj[u].size(); v++)//遍历u连接的每一条边
    
49.         {
    
50.             int id = adj[u][v].id, dis = adj[u][v].dis;
    
51. 
    
52.             if (dis + d[u] < d[id])//如果以u为前驱路径更短
    
53.             {
    
54.                 d[id] = dis + d[u];
    
55.                 num[id] = num[u];
    
56.                 w[id] = weight[id] + w[u];
    
57.                 pre[id].clear();
    
58.                 pre[id].insert(u);
    
59. 
    
60.                 if (!inq[id])//如果id不在队列中
    
61.                 {
    
62.                     q.push(id);
    
63.                     inq[id] = true;                    
    
64.                 }
    
65.             }
    
66.             else if (dis + d[u] == d[id])//如果存在等价路径
    
67.             {
    
68.                 if (weight[id] + w[u] > w[id])
    
69.                     w[id] = weight[id] + w[u];
    
70. 
    
71.                 num[id] = 0;
    
72.                
    
73.                 pre[id].insert(u);
    
74.                 for (set<int>::iterator it = pre[id].begin(); it != pre[id].end(); ++it)
    
75.                     num[id] += num[*it];
    
76.             }
    
77.         }
    
78.     }
    
79. }
    
80. 
    
81. int main(void)
    
82. {
    
83.     // freopen("input.txt", "r", stdin);
    
84.     scanf("%d %d %d %d", &n, &m, &c1, &c2);
    
85. 
    
86.     for (int i = 0; i < n; i++)
    
87.         scanf("%d", weight + i);
    
88.    
    
89.     while (m--)
    
90.     {
    
91.         int a, b, l;
    
92.         scanf("%d %d %d", &a, &b, &l);
    
93. 
    
94.         adj[a].push_back(node(b, l));
    
95.         adj[b].push_back(node(a, l));
    
96.     }
    
97. 
    
98.     SPFA(c1);
    
99. 
    
100.     printf("%d %d", num[c2], w[c2]);
     
101. 
     
102.     return 0;
     
103. }

复制代码

蒋博文

我这里没毛病啊

798236606

蒋博文 发表于 2020-2-23 18:05
我这里没毛病啊

假的

蒋博文

我只有前两个数据，

蒋博文

显示正确

798236606

蒋博文 发表于 2020-2-24 17:06
我只有前两个数据，

我不信，你肯定打开方式不对

蒋博文

我好像直接用Dev-c++运行了。。。。

一个账号

蒋博文 发表于 2020-2-23 18:05
我这里没毛病啊

骗人：

蒋博文

一个账号 发表于 2020-2-25 12:47
骗人：

我都说了，
我好像直接用Dev-c++运行了。。。。

蒋博文

蒋博文 发表于 2020-2-25 12:48
我都说了，
我好像直接用Dev-c++运行了。。。。

自己看看，别随便诬陷人

wwqq1234054

网站收下了