PTA A1003 Bellman-Ford算法统计最短路径数的两个方法，法二好使（满分），法一不太好使（扣三分）

Question

作者在跟着算法笔记学习Bellman-Ford算法时，使用该算法完成PTA的A1003题Emergency（代码如下）在统计最短路径时，由于贝尔曼福特算法会多次访问每一条边，这使得其会多次得到最短路径的前驱，故使用容器set去重。在统计最短路径数量时，使用迭代器遍历set，累加前驱的最短路径数量成功得到正确结果，而使用另一个方法在每次向set集合中插入元素时获取返回值，在插入成功时同时累加前驱结点的最短路径数量却无法总是得到正确结果，这是什么原因呢？

问题相关代码

//
// Created by BuGuWei on 2022/1/22.
//
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXV = 500, INF = 0x3fffffff;

struct Node{
    int v, dis;
    Node(int _v, int _dis) : v(_v), dis(_dis){};
};
int n, m, c1, c2, weight[MAXV];
vector<Node> Adj[MAXV];
int d[MAXV], w[MAXV] = {0}, num[MAXV] = {0};
set<int> pre[MAXV];
using namespace std;
void bellman(int s);
int main() {
    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for(int i = 0; i < n; i++) {
        scanf("%d", &weight[i]);
    }
    int a, b, l;
    for(int j = 0; j < m; j++){
        //         Node* tempNode = new Node();
        scanf("%d%d%d", &a, &b, &l);
        Adj[a].push_back(Node(b, l));
        Adj[b].push_back(Node(a, l));
    }
    //    dijkstra(c1);
    bellman(c1);
    printf("%d %d\n", num[c2], w[c2]);
    return 0;
}

void bellman(int s) {
    fill(d, d + n, INF);
    fill(w, w + n, 0);
    fill(num, num + n, 0);
    d[s] = 0;
    w[s] = weight[s];
    num[s] = 1;
    for(int i = 0; i < n; i++) {
        for(int u = 0; u < n; u++) {
            for(int j = 0; j < Adj[u].size(); j++) {
                int v = Adj[u][j].v, dis = Adj[u][j].dis;
                if(d[u] + dis < d[v]) {
                    d[v] = d[u] + dis;
                    w[v] = w[u] + weight[v];
                    num[v] = num[u];
                    pre[v].clear();
                    pre[v].insert(u);
                } else if(d[u] + dis == d[v]) {
                    if(w[u] + weight[v] > w[v]){
                        w[v] = w[u] + weight[v];
                    }

                    // 法一
                    if(pre[v].insert(u).second) {
                        num[v] += num[u];
                    }

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

}

运行结果及报错内容

法一

法二

我的解答思路

即每次插入最短路径成功时计算当前最短路径数量。

希望有da shen能刷到我的问题并斧正，万谢！

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。


因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。