HNUOJ13375花径问题(SPFA算法)

题目链接：HNUOJ 13375

任务描述：给定一个带权图，需要找到从起点到终点的所有最短路径，并计算这些路径的权重总和。

解决方案：利用SPFA（Shortest Path Faster Algorithm）算法来寻找最短路径，并在过程中记录每条路径的信息，最后汇总所有最短路径的权重。

以下是C++实现代码：

#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define MAXN 10010
#define MOD 10009
using namespace std;

struct Edge {
    int to, weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

vector edges[MAXN];
bool visited[MAXN];
int distance[MAXN];
vector paths[MAXN];

void addEdge(int from, int to, int weight) {
    edges[from].emplace_back(to, weight);
}

void spfa(int start) {
    memset(visited, false, sizeof(visited));
    fill(distance, distance + MAXN, INF);
    queue q;
    q.push(start);
    distance[start] = 0;
    visited[start] = true;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        visited[current] = false;
        for (auto &e : edges[current]) {
            if (distance[e.to] > distance[current] + e.weight) {
                distance[e.to] = distance[current] + e.weight;
                if (!visited[e.to]) {
                    visited[e.to] = true;
                    q.push(e.to);
                    paths[e.to].clear();
                    paths[e.to].push_back(current);
                }
            } else if (distance[e.to] == distance[current] + e.weight) {
                paths[e.to].push_back(current);
            }
        }
    }
}

long long totalWeight = 0;
bool visitedPath[MAXN];

void dfs(int node) {
    if (visitedPath[node]) return;
    visitedPath[node] = true;
    for (int prev : paths[node]) {
        totalWeight += edges[prev].back().weight;
        dfs(prev);
    }
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        for (int i = 0; i             edges[i].clear();
            paths[i].clear();
        }
        for (int i = 0; i             int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        spfa(0);
        memset(visitedPath, false, sizeof(visitedPath));
        totalWeight = 0;
        dfs(n - 1);
        printf("%lld\n", totalWeight * 2);
    }
    return 0;
}

上述代码中，我们首先定义了图的结构，包括节点和边。然后实现了SPFA算法来计算最短路径，并记录每个节点的前驱节点。最后，通过深度优先搜索（DFS）遍历所有可能的最短路径，计算它们的总权重。