UVa 163题解：Dijkstra算法在复杂交通网络中的应用

1. 项目概述

UVa 163 "City Directions"是ACM国际大学生程序设计竞赛(ICPC)中的一道经典图论题目。这道题最早出现在1994年的世界总决赛中，考察选手对最短路径算法和复杂城市路网建模的综合应用能力。题目背景设定在一个拥有特殊交通规则的城市中，参赛者需要编写程序计算两点之间的最短行驶时间。

这道题之所以成为经典，是因为它将Dijkstra算法的基本应用与真实城市交通中的复杂规则相结合。不同于传统的最短路径问题，City Directions需要考虑单行道、转向限制、交通信号灯等现实因素，极大增加了问题的挑战性。在ICPC圈内，这道题被公认为检验选手图论功力的"试金石"。

2. 问题核心解析

2.1 题目基本设定

题目描述一个城市的道路网络由若干个十字路口(intersection)和连接它们的道路组成。每个十字路口都有一个交通信号灯，周期性地在南北向和东西向之间切换。关键在于：

1. 每条道路都是单向的（单行道）
2. 车辆只能在绿灯方向行驶
3. 转向行为受严格限制（如某些路口禁止左转）
4. 信号灯周期各路口可能不同

2.2 输入输出规范

输入包含多个测试用例，每个用例描述如下：

• 城市名称（字符串）
• 路口数量n（2 ≤ n ≤ 20）
• 起点和终点路口编号
• 各路口信号灯周期（南北/东西方向的绿灯持续时间）
• 道路连接关系及行驶时间
• 转向限制规则

输出要求给出从起点到终点的最短时间路径，格式为：

code复制城市名称
总时间: 分钟
路径: 路口序列

2.3 问题复杂度分析

该问题的状态空间由三个维度决定：

1. 当前所在路口（n种可能）
2. 到达时间（影响信号灯状态）
3. 进入当前路口的方向（4个可能）

最坏情况下状态数为n×T×4，其中T是可能的最大时间。由于路口数n≤20且时间可离散化处理，使用优先队列优化的Dijkstra算法是可行的。

3. 解决方案设计

3.1 图模型构建

与传统最短路径问题不同，我们需要建立带有时态属性的图模型：

python复制class Intersection:
    def __init__(self):
        self.ns_green = 0   # 南北向绿灯持续时间