题目分析

需要在图中找到从起点到终点的最短路径，但有两个重要约束：

1. 油量限制：车辆最多行驶 limit 时间，只能在加油站加油
2. 红绿灯限制：最多经过 k 个红绿灯
3. 加油时间：每次加油需要额外 cost 时间

解题思路

核心思想

使用分层图 + 加油站重构的方法：

1. 分层图处理红绿灯约束：构建 $k+1$ 层图，每层代表经过的红绿灯数量
2. 加油站间重构处理油量限制：在加油站间构建新图，确保路径满足油量限制
3. Dijkstra算法求最短路：在重构后的分层图上运行最短路径算法

关键技术

• 状态编码：(红绿灯数量, 节点) 作为状态
• 图重构：只在加油站间考虑油量约束
• 平均等待时间：红绿灯的数学期望等待时间

算法步骤

1. 读入数据并建立节点映射
2. 构建分层图结构
3. 计算红绿灯平均等待时间
4. 在加油站间重构满足油量限制的图
5. 运行Dijkstra算法求解最短路径

完整代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 1.1e6 + 5;
constexpr double INF = 1e18, eps = 1e-10;

int n, m, k, limit, cost, S, T;
int id[11][MAXN / 10];  // 分层图节点编号
unordered_map<string, int> mp;  // 节点名称到编号的映射
vector<int> gas;  // 加油站节点列表
double out[MAXN];  // 每个节点的红绿灯平均等待时间

// 图结构
struct Graph {
    int head[MAXN], tot;
    struct Edge {
        int v, to;
        double w;
    } e[MAXN << 1];
    
    // 添加单向边
    void addedge(int u, int v, double w) {
        e[++tot] = {v, head[u], w};
        head[u] = tot;
    }
    
    // 添加双向边，考虑红绿灯约束
    void addf(int u, int v, double w) {
        if (fabs(out[v]) > eps) {
            // 目标节点有红绿灯，消耗一次红绿灯次数
            for (int i = 0; i < k; i++) {
                addedge(id[i][u], id[i + 1][v], w + out[v]);
            }
        } else {
            // 目标节点无红绿灯，不消耗次数
            for (int i = 0; i <= k; i++) {
                addedge(id[i][u], id[i][v], w);
            }
        }
    }
    
    double dis[MAXN];
    bool vis[MAXN];
    
    // Dijkstra算法求最短路
    void dijkstra(int s) {
        // 初始化距离数组
        for (int i = 1; i <= n * (k + 1); i++) {
            dis[i] = INF;
            vis[i] = false;
        }
        
        priority_queue<pair<double, int>, 
                      vector<pair<double, int>>,
                      greater<pair<double, int>>> q;
        dis[s] = 0;
        q.emplace(0, s);
        
        while (!q.empty()) {
            int u = q.top().second;
            q.pop();
            
            if (vis[u]) continue;
            vis[u] = true;
            
            for (int i = head[u]; i; i = e[i].to) {
                int v = e[i].v;
                double new_dis = dis[u] + e[i].w;
                if (new_dis < dis[v]) {
                    dis[v] = new_dis;
                    q.emplace(dis[v], v);
                }
            }
        }
    }
};

Graph G, GF;  // G: 原分层图, GF: 加油站重构图

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    
    // 读入基本参数
    cin >> n >> m >> k >> limit >> cost;
    
    // 构建分层图节点编号
    for (int i = 0; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            id[i][j] = i * n + j;
        }
    }
    
    // 读入节点信息
    for (int i = 1; i <= n; i++) {
        string name;
        int a, b;
        cin >> name >> a >> b;
        mp[name] = i;
        
        // 识别特殊节点
        if (name == "start" || name == "end" || name.find("gas") != string::npos) {
            gas.push_back(i);
        }
        
        if (name == "start") S = i;
        else if (name == "end") T = i;
        
        // 计算红绿灯平均等待时间
        if (a > 0) {
            // 平均等待时间公式: a² / 2(a+b)
            out[i] = 1.0 * a * a / (2.0 * (a + b));
        }
    }
    
    // 读入边信息并构建原分层图
    for (int i = 1; i <= m; i++) {
        string u_name, v_name, edge_name;
        int w;
        cin >> u_name >> v_name >> edge_name >> w;
        int u = mp[u_name], v = mp[v_name];
        
        // 添加双向边
        G.addf(u, v, w);
        G.addf(v, u, w);
    }
    
    // 在加油站间重构满足油量限制的图
    for (auto x : gas) {
        // 从加油站x出发，计算到所有节点的最短距离
        G.dijkstra(id[0][x]);
        
        for (auto y : gas) {
            if (x == y) continue;
            
            // 计算加油时间（起点终点加油不花时间）
            int add_cost = (x != S && x != T) ? cost : 0;
            
            // 在油量限制内构建新边
            for (int i = 0; i <= k; i++) {
                if (G.dis[id[i][y]] <= limit) {
                    for (int j = 0; i + j <= k; j++) {
                        GF.addedge(id[j][x], id[i + j][y], 
                                 G.dis[id[i][y]] + add_cost);
                    }
                }
            }
        }
    }
    
    // 在重构图上运行Dijkstra求最短路径
    GF.dijkstra(id[0][S]);
    
    // 找出所有层中的最小距离
    double ans = INF;
    for (int i = 0; i <= k; i++) {
        ans = min(ans, GF.dis[id[i][T]]);
    }
    
    cout << fixed << setprecision(3) << ans << '\n';
    return 0;
}

代码说明

关键数据结构

• id[i][j]：第 $i$ 层第 $j$ 个节点的全局编号
• Graph 结构：包含邻接表实现的图结构
• out[i]：节点 $i$ 的红绿灯平均等待时间

算法核心

1. 分层图构建

for (int i = 0; i <= k; i++)
    for (int j = 1; j <= n; j++)
        id[i][j] = i * n + j;

构建 $k+1$ 层图，每层代表经过的不同红绿灯数量。

2. 红绿灯处理

if (fabs(out[v]) > eps) {
    // 消耗红绿灯次数
    for (int i = 0; i < k; i++)
        addedge(id[i][u], id[i + 1][v], w + out[v]);
} else {
    // 不消耗次数
    for (int i = 0; i <= k; i++)
        addedge(id[i][u], id[i][v], w);
}

3. 加油站间重构

for (auto x : gas) {
    G.dijkstra(id[0][x]);
    for (auto y : gas) {
        if (G.dis[id[i][y]] <= limit) {
            // 在油量限制内添加边
            GF.addedge(id[j][x], id[i + j][y], 
                     G.dis[id[i][y]] + add_cost);
        }
    }
}

数学原理

红绿灯平均等待时间：

• 红灯时长 $a$，绿灯时长 $b$
• 平均等待时间 = $\frac{a^2}{2(a+b)}$
• 这个公式基于均匀分布的数学期望

复杂度分析

• 空间复杂度：$O(k \cdot n + m)$
• 时间复杂度：
  • 预处理：$O(|gas| \cdot k \cdot (n \log n + m))$
  • 主算法：$O(k \cdot n \log n)$
  • 其中 $|gas| \leq 50$，$k \leq 10$，$n \leq 10000$