题解 P4568 【[JLOI2011]飞行路线】

2018-10-30 10:42:38


分层图最短路板子题。

对于图中的每个结点 $u$,可以把它拆成 $k + 1$ 个节点 $u_j, j \in [0, k]$,分别表示当使用 $j$ 次免费通行权限后到达 $u$ 号节点的状态。对于样例,则可以这样表示(图画得不是很好,见谅):

pic

图中加粗结点表示样例的起点和终点。

事实上,虽然样例可以用这种方法画图表示,但我们写代码的时候不一定要建这么多结点。只需要按照原始的输入建普通的图。考虑 dp。设 $\text{dis}_{i, j}$ 表示当前从起点 $i$ 号结点,使用了 $j$ 次免费通行权限后的最短路径。显然,$\text{dis}$ 数组可以这么转移:

$$ \text{dis}_{i, j} = \min\{\min\{\text{dis}_{from, j - 1}\}, \min\{\text{dis}_{from,j} + w\}\} $$

其中,$from$ 表示 $i$ 的父亲节点,$w$ 表示当前所走的边的边权。当 $j - 1 \geq k$ 时,$\text{dis}_{from, j}$ = $\infty$。

事实上,这个 dp 就相当于对于每个结点的 $k + 1$ 个状态,想象成拆为 $k + 1$ 个不同的结点,每个结点之间可以相连,仿佛这张图一共有 $k + 1$ 层。

对于进行 Dijkstra 算法的过程,把 $\text{done}$ 数组也开成二维就好,每次入队的时候分别判断能否使用免费通行权限即可。最后统计答案的时候需要统计出到最后一个结点总共 $k + 1$ 种状态的最短距离。

核心代码如下:

struct State { // 优先队列的结点结构体
    int v, w, cnt; // cnt 表示已经使用多少次免费通行权限
    State() {}
    State(int v, int w, int cnt) : v(v), w(w), cnt(cnt) {}
    bool operator<(const State &rhs) const { return w > rhs.w; }
};

void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[s][0] = 0;
    pq.push(State(s, 0, 0)); // 到起点不需要使用免费通行权,距离为零
    while (!pq.empty()) {
        const State top = pq.top(); pq.pop();
        int u = top.v, nowCnt = top.cnt;
        if (done[u][nowCnt]) continue;
        done[u][nowCnt] = true;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v, w = edge[i].w;
            if (nowCnt < k && dis[v][nowCnt + 1] > dis[u][nowCnt]) { // 可以免费通行
                dis[v][nowCnt + 1] = dis[u][nowCnt];
                pq.push(State(v, dis[v][nowCnt + 1], nowCnt + 1));
            }
            if (dis[v][nowCnt] > dis[u][nowCnt] + w) { // 不可以免费通行
                dis[v][nowCnt] = dis[u][nowCnt] + w;
                pq.push(State(v, dis[v][nowCnt], nowCnt));
            }
        }
    }
}

int main() {
    n = read(), m = read(), k = read(); 
    // 笔者习惯从 1 到 n 编号,而这道题是从 0 到 n - 1,所以要处理一下 
    s = read() + 1, t = read() + 1;
    while (m--) {
        int u = read() + 1, v = read() + 1, w = read();
        add(u, v, w), add(v, u, w); // 这道题是双向边 
    }
    dijkstra();
    int ans = std::numeric_limits<int>::max(); // ans 取 int 最大值为初值
    for (int i = 0; i <= k; ++i)
        ans = std::min(ans, dis[t][i]); // 对到达终点的所有情况取最优值 
    println(ans);
}