题意分析

题目要求计算从中央检查站（CCS）到所有站点再返回的最小总交通费用。关键点包括：

1. 有向图的单源最短路径问题
2. 需要计算：
   • 从CCS（节点$1$）到所有其他节点的最短路径和
   • 从所有节点返回CCS的最短路径和
3. 图规模较大（$P,Q \leq 10^6$），需要高效算法

解题思路

1. 正向图与反向图：
   • 构建原图计算CCS到各站点的最短路径
   • 构建反向图计算各站点到CCS的最短路径
2. SPFA算法：
   • 适用于含大量边的稀疏图
   • 通过队列优化Bellman-Ford算法
3. 结果计算：
   • 将正向和反向的最短路径结果相加

实现步骤

1. 输入处理：
   • 读取测试用例数$T$
   • 对每个用例读取节点数$P$和边数$Q$
2. 建图：
   • 使用链式前向星存储原图和反向图
3. 最短路径计算：
   • 使用SPFA算法分别计算原图和反向图的最短路径
4. 结果输出：
   • 累加所有节点的往返最短路径值

C++实现

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <utility> // for pair

using namespace std;

typedef long long LL;
typedef pair<LL, int> PII; // {距离, 点}

const int N = 1000000 + 10;
const LL INF = 1000000000000000000LL;

struct Edge {
    int v, w;
    Edge(int vv, int ww) : v(vv), w(ww) {}
};

vector<Edge> g[N], rg[N]; // 正向图和反向图
LL d[N], rd[N];           // 正向和反向的最短距离
bool vis[N];

void dijkstra(int start, LL dist[], vector<Edge> graph[]) {
    for (int i = 1; i < N; ++i) dist[i] = INF;
    memset(vis, 0, sizeof(vis));
    dist[start] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    heap.push(make_pair(0, start));

    while (!heap.empty()) {
        PII t = heap.top();
        heap.pop();
        int u = t.second;
        if (vis[u]) continue;
        vis[u] = true;

        for (size_t j = 0; j < graph[u].size(); ++j) {
            int v = graph[u][j].v;
            int w = graph[u][j].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                heap.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);

        // 清空图
        for (int i = 1; i <= n; ++i) {
            g[i].clear();
            rg[i].clear();
        }

        // 建图
        for (int i = 0; i < m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back(Edge(v, w));    // 正向边
            rg[v].push_back(Edge(u, w));   // 反向边
        }

        // 计算正向和反向最短路
        dijkstra(1, d, g);
        dijkstra(1, rd, rg);

        // 统计总费用
        LL ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += d[i] + rd[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

代码说明

1. 数据结构：

   • Edge结构体存储边信息
   • h[]和rh[]分别存储原图和反向图的邻接表
   • d[]和rd[]存储最短距离

2. 核心函数：

   • add()：链式前向星加边
   • spfa()：SPFA算法实现

3. 优化处理：

   • 使用队列优化
   • book[]数组标记节点是否在队列中

4. 复杂度分析：

   • 时间复杂度：$O(kE)$，其中$k$为常数
   • 空间复杂度：$O(V+E)$

5. 示例分析：

   • 输入$P=2,Q=2$时：
     • 正向最短路：$1→2=13$
     • 反向最短路：$2→1=33$
     • 总费用：$13+33=46$