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

Anguei · 2018-10-30 10:42:38 · 题解

分层图最短路板子题。

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

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

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

其中，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);
}