题解：P13515 [KOI 2025 #1] 木槿花开了

· · 题解

由题目可知：不可以在睁眼时在道路或有窗房内停留，而闭眼时在哪里都可以。问从点 1 出发到点 n 的最短耗时。本题解使用了 Dijkstra、邻接表存图。

Dijkstra 是一种求解非负权图上单源最短路径的算法。将结点分成两个集合：已确定最短路长度的点集（记为 S 集合）的和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合.初始化 dis_𝑠=0，其他点的 𝑑𝑖𝑠 均为 +∞。然后重复这些操作：从 𝑇 集合中，选取一个最短路长度最小的结点，移到 𝑆 集合中。对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。直到 𝑇 集合为空，算法结束。——oi.wiki

如果屋子有窗就不能在这里停留，否则可以在这里停留（当然也可以不停留）。从点 1 出发，先遍历所有点到点 1 的最短路，再计算所有点到点 n 的最短路。最后求出答案。

实现代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;                          // 最大建筑数
const long long INF = 0x3f3f3f3f3f3f3f3f;       // 无穷大
long long n, m, c[N], A, B, dis[N];
// 原图：道路信息
struct edge { long long to, val; };
vector<edge> a1[N];// 原图邻接表
vector<edge> a2[N];// 新图：仅包含无窗户建筑之间的可达边
// Dijkstra 优先队列节点
struct node {
    long long ix, d;                          // ix: 当前建筑编号, d: 到达该建筑的时间
    bool operator<(node x) const { return d > x.d; }  // 小根堆
};
/*
  dis1(id): 从无窗户建筑 id（或 id 自身）出发，在原图上跑 Dijkstra。
  限制：中间节点只能经过有窗户的建筑（c[x]==1），
  即跳过除起点外的其他无窗户建筑作为中转。
  这样得到的 dis[j] 就是从 id 到 j 且中间不经过其他无窗户建筑的最短距离。
 */
void dis1(long long id) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node> q;
    dis[id] = 0;
    q.push((node){id, 0});
    while (!q.empty()) {
        node qwq = q.top(); q.pop();
        long long x = qwq.ix, d = qwq.d;
        if (d > dis[x]) continue;              // 已过时的状态，跳过
        // 关键：如果不是起点，且当前建筑是无窗户的，则不能作为中转
        if (x != id && !c[x]) continue;
        for (long long i = 0; i < a1[x].size(); i++) {
            long long y = a1[x][i].to, w = a1[x][i].val;
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                q.push({y, dis[y]});
            }
        }
    }
}
/*
  dis2(): 在新图 a2（仅含无窗户建筑）上跑 Dijkstra。
  考虑闭眼/睁眼周期来计算实际到达时间。
  当前在节点 x，时间为 d，要走权值为 w 的边到 y：
    r = d % (A+B) 表示当前时间在周期内的偏移量。
    若 r + w <= A：当前闭眼周期内剩余时间足够走完这条边 -> 到达时间 d+w。
 *  否则：需要等到下一个闭眼周期开始再出发 -> 到达时间 = 下一周期起点 + w。
 */
void dis2() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node> q;
    dis[1] = 0;
    q.push((node){1, 0});
    while (!q.empty()) {
        node qwq = q.top(); q.pop();
        long long x = qwq.ix, d = qwq.d;
        if (d > dis[x]) continue;
        for (long long i = 0; i < a2[x].size(); i++) {
            long long y = a2[x][i].to, w = a2[x][i].val;
            long long r = d % (A + B);          // 当前时刻在周期内的偏移
            long long qqq;                      // 到达 y 的实际时间
            if (r + w <= A)                     // 闭眼期内能走完
                qqq = d + w;
            else                                // 等下一个闭眼周期
                qqq = (d / (A + B) + 1) * (A + B) + w;
            if (dis[y] > qqq) {
                dis[y] = qqq;
                q.push({y, qqq});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (long long i = 1, a, b, c; i <= m; i++) {
        cin >> a >> b >> c;
        a1[a].push_back((edge){b, c});          // 原图：单向边
    }
    for (long long i = 1; i <= n; i++) cin >> c[i];  // 窗户信息
    cin >> A >> B;                                   // 闭眼/睁眼时长
    // ---- 建新图 a2 ----
    // 枚举每个无窗户建筑（不含 c[i]==1 的），计算其到其他无窗户建筑的可达性
    for (long long i = 1; i <= n; i++) {
        if (c[i]) continue;                     // 有窗户的建筑不能作为停留点
        dis1(i);                                // 计算从 i 出发的最短距离
        for (long long j = 1; j <= n; j++)
            // i≠j，j 也无窗户，且一次闭眼周期内可达
            if (i != j && !c[j] && dis[j] <= A)
                a2[i].push_back({j, dis[j]});
    }
    // ---- 在新图上跑带周期约束的最短路 ----
    dis2();
    if (dis[n] == INF) cout << "-1";
    else cout << dis[n];
    return 0;
}

感谢观看。