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

798236606

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

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

C++代码：

#include <cstdio>
#include <climits>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

const int maxn = 510;

typedef struct node{
    int id, dis;

    node (int _id, int _dis) : id(_id), dis(_dis) {};
}Node;

int n, m, c1, c2;
int weight[maxn];//存放点权，即救援队数
int num[maxn];//存放到每个点的最短路径数
int w[maxn];//存放可聚集的队伍数
int d[maxn];//存放最短路径长度
bool inq[maxn];//是否在队列内
vector<Node> adj[maxn];//邻接表
set<int> pre[maxn];//存放顶点在最短路径中的前驱

void SPFA(int s)
{
    fill(d, d + n, INT_MAX);
    memset(w, 0, sizeof(w));
    memset(num, 0, sizeof(num));
    memset(inq, false, sizeof(inq));

    queue<int> q;
    q.push(s);
    w[s] = weight[s];
    d[s] = 0;
    num[s] = 1;
    inq[s] = true;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u] = false;

        for (int v = 0; v < adj[u].size(); v++)//遍历u连接的每一条边
        {
            int id = adj[u][v].id, dis = adj[u][v].dis;

            if (dis + d[u] < d[id])//如果以u为前驱路径更短
            {
                d[id] = dis + d[u];
                num[id] = num[u];
                w[id] = weight[id] + w[u];
                pre[id].clear();
                pre[id].insert(u);

                if (!inq[id])//如果id不在队列中
                {
                    q.push(id);
                    inq[id] = true;                    
                }
            }
            else if (dis + d[u] == d[id])//如果存在等价路径
            {
                if (weight[id] + w[u] > w[id])
                    w[id] = weight[id] + w[u];

                num[id] = 0;
                
                pre[id].insert(u);
                for (set<int>::iterator it = pre[id].begin(); it != pre[id].end(); ++it)
                    num[id] += num[*it];
            }
        }
    }
}

int main(void) 
{
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d %d", &n, &m, &c1, &c2);

    for (int i = 0; i < n; i++)
        scanf("%d", weight + i);
    
    while (m--)
    {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);

        adj[a].push_back(node(b, l));
        adj[b].push_back(node(a, l));
    }

    SPFA(c1);

    printf("%d %d", num[c2], w[c2]);

    return 0;
}

蒋博文

我这里没毛病啊

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

网站收下了