题解：洞穴突袭者（Cave Raider）

一、题目分析

本题要求在带有时间限制的隧道网络中，找到从起点到终点的最短路径，其中隧道在特定时间段内会被关闭（清理），进入关闭中的隧道会导致死亡。因此，路径规划需确保通过隧道的时间完全在其开启时间段内。

二、解题思路

1. 图模型构建：
   将每个洞穴视为图的节点，隧道视为无向边。每条边需记录以下信息：

   • 连接的目标节点（v）
   • 通过隧道所需时间（ct）
   • 隧道的开启/关闭时间序列（ti[j][0]为开启时间，ti[j][1]为关闭时间，交替出现）。

2. 时间状态扩展：
   使用 广度优先搜索（BFS）或最短路径算法（如SPFA） 处理时间状态。每个节点的状态包含当前所在洞穴和到达该洞穴的时间，目标是找到到达终点的最小时间。

3. 隧道通过条件判断：
   对于当前时间 t 到达节点 u，尝试通过边 u→v：

   • 遍历隧道的所有开启时间段，找到第一个满足以下条件的区间 [open, close)：
     • t 到达 u 后，进入隧道的时间 t 需 ≥ open（隧道已开启）。
     • 通过隧道的总时间 t + ct 需 < close（隧道未关闭）。
   • 若存在这样的区间，计算到达 v 的时间为 max(t, open) + ct，并更新 v 的最短到达时间。

4. SPFA算法应用：
   使用 SPFA（Shortest Path Faster Algorithm）处理带时间状态的最短路径问题，队列维护待松弛的节点，记录每个节点的最短到达时间，避免重复计算。

三、代码实现

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX_N = 55;    // 最大洞穴数
const int MAX_M = 505;   // 最大隧道数

struct Edge {
    int v;             // 目标节点
    int ct;            // 通过隧道所需时间
    int ti[20][2];     // 开启/关闭时间区间（最多20个区间）
    int ways;          // 时间区间数量（ways = 区间数 - 1，最后一个区间可能无限长）
    int next;          // 邻接表下一条边
} e[MAX_M * 2];       // 无向图，每条隧道对应两条边（双向）

int idx, head[MAX_N]; // 邻接表指针
int dis[MAX_N];       // 到达各节点的最短时间
bool vis[MAX_N];      // 节点是否在队列中

// 插入双向边（无向图）
void add_edge(int u, int v, int ct, int* schedule, int len) {
    // 处理正向边 u→v
    idx++;
    e[idx].v = v;
    e[idx].ct = ct;
    e[idx].ways = 0; // 区间数量初始化为0
    int j = 0;
    // 填充时间区间（每两个数为一个关闭-开启对，最后可能有一个单独的关闭时间）
    for (; j + 1 < len; j += 2) {
        e[idx].ti[e[idx].ways][0] = schedule[j];   // 关闭时间（区间开始）
        e[idx].ti[e[idx].ways][1] = schedule[j+1]; // 开启时间（区间结束）
        e[idx].ways++;
    }
    // 处理最后一个可能的关闭时间（无后续开启，即永远关闭）
    if (j < len) {
        e[idx].ti[e[idx].ways][0] = schedule[j];
        e[idx].ti[e[idx].ways][1] = INF; // 标记为无限长关闭区间
        e[idx].ways++;
    }
    e[idx].next = head[u];
    head[u] = idx;

    // 处理反向边 v→u（对称）
    idx++;
    e[idx].v = u;
    e[idx].ct = ct;
    e[idx].ways = 0;
    j = 0;
    for (; j + 1 < len; j += 2) {
        e[idx].ti[e[idx].ways][0] = schedule[j];
        e[idx].ti[e[idx].ways][1] = schedule[j+1];
        e[idx].ways++;
    }
    if (j < len) {
        e[idx].ti[e[idx].ways][0] = schedule[j];
        e[idx].ti[e[idx].ways][1] = INF;
        e[idx].ways++;
    }
    e[idx].next = head[v];
    head[v] = idx;
}

// SPFA算法求解最短时间
void spfa(int start, int end, int n) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    queue<int> q;
    dis[start] = 0;
    vis[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;

        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            int ct = e[i].ct;
            int ways = e[i].ways;

            for (int j = 0; j <= ways; j++) {
                int open = e[i].ti[j][0];  // 隧道开启时间（允许进入的最早时间）
                int close = e[i].ti[j][1]; // 隧道关闭时间（不允许停留到该时间）

                // 检查当前时间是否可以进入隧道
                if (dis[u] >= close) continue; // 到达u时隧道已关闭，无法进入
                if (dis[u] + ct <= open) {     // 到达u的时间太早，需等待到open时间才能进入
                    int enter_time = open;
                    int arrive_time = enter_time + ct;
                    if (arrive_time < close && arrive_time < dis[v]) {
                        dis[v] = arrive_time;
                        if (!vis[v]) {
                            q.push(v);
                            vis[v] = true;
                        }
                    }
                } else if (dis[u] < close) {  // 到达u的时间在开启区间内，可以立即进入
                    int arrive_time = dis[u] + ct;
                    if (arrive_time < close && arrive_time < dis[v]) {
                        dis[v] = arrive_time;
                        if (!vis[v]) {
                            q.push(v);
                            vis[v] = true;
                        }
                    }
                }
            }
        }
    }
}

int main() {
    int n, m, s, t;
    while (cin >> n && n != 0) {
        cin >> m >> s >> t;
        idx = -1;
        memset(head, -1, sizeof(head)); // 初始化邻接表

        for (int i = 0; i < m; i++) {
            string line;
            getline(cin, line);
            if (line.empty()) continue; // 处理可能的空行

            // 解析输入行
            int u, v, ct;
            int schedule[40], len = 0;
            char* token = strtok(&line[0], " ");
            u = atoi(token);
            token = strtok(NULL, " ");
            v = atoi(token);
            token = strtok(NULL, " ");
            ct = atoi(token);
            schedule[len++] = ct; // 占位，实际ct已单独提取，后续覆盖

            while (token != NULL) {
                token = strtok(NULL, " ");
                if (token != NULL) {
                    schedule[len++] = atoi(token);
                }
            }
            // 重新构造时间序列（前两个数为u, v，第三个数为ct，后续为关闭-开启时间）
            int* times = new int[len - 2]; // 跳过u, v, ct，提取后续时间
            for (int j = 0; j < len - 3; j++) {
                times[j] = schedule[j + 3]; // schedule[0]=u, schedule[1]=v, schedule[2]=ct
            }
            add_edge(u, v, ct, times, len - 3); // len-3为时间序列的长度（关闭-开启对的数量）
            delete[] times;
        }

        spfa(s, t, n);
        if (dis[t] == INF) {
            cout << "*" << endl;
        } else {
            cout << dis[t] << endl;
        }
    }
    return 0;
}

四、代码解析

1. 输入解析与建图：

   • 使用 getline 读取整行输入，通过 strtok 分割字符串，提取隧道的连接节点、通过时间和清理时间表。
   • 每条隧道作为无向边处理，生成两条反向边（u→v 和 v→u），每条边存储时间区间列表。

2. 时间区间处理：

   • 时间区间以 [open, close) 表示，其中 open 是隧道开启时间（允许进入），close 是关闭时间（不允许停留到该时刻）。
   • 最后一个区间可能只有关闭时间（无后续开启），视为永久关闭，用 INF 表示无限长关闭时间。

3. SPFA算法松弛条件：

   • 对于每个节点 u 的当前到达时间 dis[u]，遍历所有邻接边的时间区间，判断是否能在该区间内通过隧道。
   • 若需要等待到 open 时间进入，则计算等待后的进入时间和到达目标节点的时间；若当前时间已在区间内，则直接计算到达时间。
   • 若新的到达时间更优，则更新 dis[v] 并将 v 加入队列。

4. 边界处理：

   • 起点与终点相同时，直接输出0。
   • 若终点无法到达，输出*。

五、关键点总结

• 时间状态建模：将时间作为状态的一部分，通过SPFA算法动态更新最短到达时间。
• 区间合法性判断：确保通过隧道的时间完全在开启区间内，避免进入关闭中的隧道。
• 无向图处理：每条隧道对应两条反向边，分别处理两个方向的通过时间和区间。

该解法通过扩展SPFA算法处理时间约束，高效地解决了带时间限制的最短路径问题，适用于题目给定的数据范围（节点数≤50，边数≤500）。