洛谷P1685：图论算法实战-计算桃花岛所有不同游览路径的总耗时

一、问题分析

桃花岛游览问题要求我们计算从起点到终点的所有不同路径的总耗时，包括每次游览后的乘船返回时间。这是一个典型的有向无环图(DAG)路径计数和耗时计算问题。

二、算法选择

由于图是无环的，我们可以使用拓扑排序来线性处理节点，同时结合动态规划来计算：

1. 到每个节点的路径数量

2. 到每个节点的总耗时

三、关键思路

1. ‌路径计数‌：使用动态规划记录到每个节点的路径数

2. ‌耗时计算‌：累计每条路径的耗时，并考虑路径间的共享部分

3. ‌往返时间‌：每次游览后需要乘船返回，这部分时间与路径数相关

四、完整代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MOD = 10000;

struct Edge {
    int to;     // 目标节点
    int time;   // 耗时
};

int main() {
    int n, m, s, t, t0;
    cin >> n >> m >> s >> t >> t0;
    
    vector<vector<Edge>> graph(n+1);  // 邻接表存储图
    vector<int> inDegree(n+1, 0);     // 入度数组
    vector<int> pathCount(n+1, 0);    // 到每个节点的路径数
    vector<int> totalTime(n+1, 0);    // 到每个节点的总耗时
    
    // 读取边并构建图
    for (int i = 0; i < m; i++) {
        int x, y, time;
        cin >> x >> y >> time;
        graph[x].push_back({y, time});
        inDegree[y]++;
    }
    
    // 拓扑排序
    queue<int> q;
    pathCount[s] = 1;  // 起点路径数为1
    
    // 初始化队列，入度为0的节点入队
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (const Edge& e : graph[u]) {
            int v = e.to;
            int time = e.time;
            
            // 更新路径数和总耗时
            pathCount[v] = (pathCount[v] + pathCount[u]) % MOD;
            totalTime[v] = (totalTime[v] + totalTime[u] + pathCount[u] * time) % MOD;
            
            // 入度减1，若为0则入队
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 计算总耗时：所有路径耗时 + 往返次数 * 船耗时
    int total = (totalTime[t] + (pathCount[t] - 1) * t0) % MOD;
    cout << total << endl;
    
    return 0;
}

五、代码讲解

1. ‌图表示‌：使用邻接表存储图结构

2. ‌拓扑排序‌：处理节点的顺序保证无后效性

3. ‌动态规划‌：

• pathCount数组记录到每个节点的路径数

• totalTime数组记录到每个节点的总耗时

4. ‌结果计算‌：总耗时=所有路径耗时+往返次数×船耗时