2020牛客暑期多校训练营（第五场）A

题目描述

You are now in a big factory. The factory could be recognized as a graph with n vertices and m edges. Every edge has its length. You have $k$ missions to do. The $i$ -th mission is going to vertex $a_i$ , picking a block and then sending it to vertex $b_i$ . You should complete the missions in the order from $1$ -st to $k$ -th. Initially you are standing at vertex $1$ .
You have a gun in your hand. When you are at some vertex $u$ , you could shoot the gun at the ground, and then a portal will be built at vertex $u$ . When there are two portals in the factory, assuming they are at $u$ and $v$ , you could transfer between $u$ and $v$ with no cost (just like an edge connecting $u$ and $v$ with length $0$ ).
You also have a remote controller in your hand. It allows you to close a portal whenever you want and wherever you are (closing one portal at a time, not all portals at the same time). What's more, there could be at most two existing portals. So if you want to create another portal when there exists two, you must use your controller to close one before you create.
You need to find the minimum distance you have to walk in order to complete all $k$ missions.

输入描述

First line contains three positive integers $n, m, k$ separated by spaces.
Next $m$ lines, each contains three integers $u_i, v_i, w_i$ , indicating a bidirectional edge connecting vertex $u_i$ and $v_i$ with length $w_i$ .
Next $k$ lines, each contains two intergers $a_i, b_i$ , indicating the begin and the end of the $i$ -th mission.
$1 \leqslant n \leqslant 300$ , $1 \leqslant m \leqslant 40000$ , $1 \leqslant k \leqslant 300$ .
$1 \leqslant u_i, v_i \leqslant n$ , $0 \leqslant w_i \leqslant 10^9$ .
$1 \leqslant a_i, b_i \leqslant n$ .
The graph is guaranteed to be connected.

输出描述

Output one integer indicating the minimum distance.

示例1

输入

输出

说明

Solution for sample $1$ : walk from $1$ to $5$ , create portals at $2$ and $4$ when passing by, and then walk from $5$ to $4$ , then you could use portals to complete the second mission.

示例2

输入

输出

示例3

输入

输出

分析

用动态规划求解。
$f(i,u,x,y)$ 表示已经完成了第 $i$ 个任务，当前人在节点 $u$ ，传送门在节点 $x$ 和 $y$ 时，行走的最短距离。状态过多，显然会 $\text{MLE}$ 和 $\text{TLE}$ 。
贪心地思考，一直创建两个传送门是没有必要的：若要从 $x$ 传送到 $y$ ，当前节点为 $u$ ，那么必须要从 $u$ 走到 $x$ 再传送到 $y$ ；不妨只在 $y$ 创建一个传送门，走到 $x$ 后再设置传送门；也就是说，我们可以随时在当前节点创建传送门。因此，只需要在状态中记录一个传送门的位置即可。 $f(i,u,p)$ 表示已经完成了第 $i$ 个任务，当前人在节点 $u$ ，传送门在节点 $p$ 时，行走的最短距离。需要继续精简状态。
不妨将 $k$ 个任务看作一条路径： $1\to a_1\to b_1\to\cdots\to a_n\to b_n$ 。一共有 $t=2k+1$ 个节点， $c_i$ 表示第 $i$ 个节点，其中 $1\leqslant i\leqslant t$ 。 $f(i,p)$ 表示当前人位于节点 $c_i$ ，传送门位于节点 $p$ 时，行走的最短距离。
可以证明，只需要三种转移，即可覆盖所有状态：① 直接从 $c_{i-1}$ 走到 $c_i$ ，不更改传送门位置；② 枚举 $q$ ，将传送门的位置更改到 $q$ ，从 $c_{i-1}$ 传送到 $p$ ，再从 $p$ 走到 $q$ ，将传送门放在 $q$ ，再从 $q$ 走到 $c_i$ ；③ 枚举 $q$ ，将传送门的位置更改到 $q$ ，从 $c_{i-1}$ 走到 $q$ ，将传送门放在 $q$ ，再从 $q$ 传送到 $p$ ，从 $p$ 走到 $c_i$ 。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem A
Date: 8/24/2020
Description: Dynamic Programming
*******************************************************************/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=705;
//====================
//f[i][j]表示：
// 当前在c[i]，传送门在j时；
// 行走的最小路程。
ll f[N][N];
ll dis[N][N];
int c[N];
int n,m;
int t;
int main(){
    int i,j,k;
    cin>>n>>m>>k;
    memset(f,inf,sizeof(f));
    memset(dis,inf,sizeof(dis));
    for(i=1;i<=n;i++) dis[i][i]=0;
    for(i=1;i<=m;i++){
        int u,v;
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        dis[u][v]=min(dis[u][v],w);
        dis[v][u]=min(dis[v][u],w);
    }
    c[++t]=1;
    for(i=1;i<=k;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        c[++t]=a;
        c[++t]=b;
    }
    //Floyed算法求(x,y)之间的最短路
    for(k=1;k<=n;k++){
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
            }
        }
    }
    for(i=1;i<=n;i++){
        //初始化
        //当前在c[1]
        //传送门设置在i
        f[1][i]=dis[1][i];
    }
    int p,q;
    for(i=2;i<=t;i++){
        //当前在c[i-1]，要走向c[i]
        for(p=1;p<=n;p++){
            //当前传送门在p
            //不改变传送门位置，直接走到 c[i]
            f[i][p]=min(f[i][p],f[i-1][p]+dis[c[i-1]][c[i]]);
            for(q=1;q<=n;q++){
                //从c[i-1]传送到p，路程0
                //从p走到q，路程dis[p][q]
                //从q走到a[i]，路程dis[q][c[i]]
                f[i][q]=min(f[i][q],f[i-1][p]+dis[p][q]+dis[q][c[i]]);
                //从c[i-1]走到q，路程dis[c[i-1]][q]
                //从q传送到p，路程为0
                //从p走到c[i]，路程dis[q][c[i]]
                f[i][q]=min(f[i][q],f[i-1][p]+dis[c[i-1]][q]+dis[p][c[i]]);
            }
        }
    }
    ll ans=inf;
    for(i=1;i<=n;i++){
        ans=min(f[t][i],ans);
    }
    cout<<ans<<endl;
    return 0;
}