牛客多校第五场 A Portal

题意：

先买游戏(bushi

按顺序完成K个任务，每个任务有要求的起始点和到达点, 途中你能建立传送门，只能建立两个，超过得远程关闭之前的传送门，建立传送门，穿越传送门，关闭传送门均无消耗

题解：

按照bxzy的题解就行状态精简

由最暴力的f[i][u][a][b] 完成了i个任务，当前在u点，传送门在a和b点

由如果要使用传送门肯定是在当前节点建立传送门传送到另一个传送门，可精简为f[i][u][a]

又由观察，u其实不用记录，每次都在任务节点上开始移动， 将任务拆分成由一个任务节点移动到另外一个任务节点

例： k = 2, a -> b, c -> d 可拆解为1->a->b->c->d四个任务

当前状态为f[i][a]

先预处理出不用传送门两点间距离，初始状态只用f[0][1]有效, 只能在1建立传送门

然后每次任务都枚举上一次任务留下的传送门在哪里，和这次要把传送门放在哪里进行状态更新

状态转移为 ：

• 不改变上一次的遗留传送门位置，直接从上一次的任务节点直接走到目标任务节点
• 从上一次任务节点走到这次要放传送门的位置，再穿越传送门走到任务节点
• 从上一次任务节点走到这次要放传送门的位置，直接走到任务节点

每一行动开始都能选择一开始的时候时候使用传送门

由此dp完成，最后遍历得到答案即可

完整代码

signed main() {
    #if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
    int n, m, k; cin >> n >> m >> k;
    memset(d, inf, sizeof d);
    rep (i, n + 1) d[i][i] = 0;
    rep (i, m) {
        int u, v; ll w; cin >> u >> v >> w;
        cmin(d[u][v], w);
        cmin(d[v][u], w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++) if (k != i)
            for (int j = 1; j <= n; j++) if (j != k and j != i)
                cmin(d[i][j], d[i][k] + d[k][j]);
    ll ans = linf;
    memset(f, inf, sizeof f);
    p[0] = 1; f[0][1] = 0;
    for (int i = 1; i <= k * 2; i++) {
        cin >> p[i];
        for (int j = 1; j <= n; j++) {
            cmin(f[i][j], f[i - 1][j] + min(d[p[i - 1]][p[i]], d[j][p[i]]));
            for (int k = 1; k <= n; k++) if(k != j) {
                cmin(f[i][k], f[i - 1][j] + min(d[j][k] + d[k][p[i]],
                                                d[p[i - 1]][k] +
                                                min(d[k][p[i]], d[j][p[i]])));
            }
        }
    }
    for (int i = 1; i <= n; i++) cmin(ans, f[k * 2][i]);
    cout << ans << endl;

    return 0;
}