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

题目大意

从点1出发，你要按顺序完成k个任务，每个任务有要求的起点终点。
途中你可以在所在的位置建立一个传送门，而同时只能用两个传送门存在，如果超过两个，则必须（远程）关闭任意一个传送门。

解题思路

一

首先可以想到，所谓的k个任务有起点终点，就是按顺序走过2k个点，a->b,c->d这样的两个任务，可以转化为走过1->a->b->c->d这条路径。
先想到一种暴力操作，每次求出dp[i][x][a][b]，表示已经完成i个任务，当前在x点，传送门分别在a,b。

二

如果我们要使用传送门来少走点路，肯定是走到一个接近x的传送门，在传送到接近终点的传送门。
但是直接在x建立一个传送门岂不是更偷懒，所以我们不必记录两个传送门，只需记录远的一个即可。这样就可以简化为dp[i][x][b]。

三

脑袋一拍，现在所在的点x也不用记录，我们在输入时将节点排成一行（就是第一句的思想），用数组a记录每个点；所以又可以简化为dp[i][b]（当前在a[i]）。
每次任务都枚举上一次任务留下的传送门位置，和这次传送门放在哪里来状态更新。

四

可以简化得到三种状态转移：（有点复杂）

• 直接从a[i]走到a[i+1]；
• 枚举走到a[i+1]后传送门的位置，设它的位置为t。
  从a[i]走到t，将传送门放在t，再从t传送到b（另一个传送门），走到a[i+1]；
• 从a[i]传送到b，在从b走到t，将传送门放在t，再从t走到啊a[i+1]。

按照上面的做法，直接先用Floyd的思路求最短路，再加dp即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
long long g[310][310],dp[610][610],ans=1e16,z;
int a[610],n,m,k;
int main()
{
    int t=1,x,y,i,j;
    scanf("%d%d%d",&n,&m,&k);
    a[1]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j) g[i][j]=0;
            else g[i][j]=1e16;
    for(i=2;i<=n;i++) dp[1][i]=1e16;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%lld",&x,&y,&z);
        g[x][y]=g[y][x]=min(g[x][y],z);
    }
    for(i=1;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        a[++t]=x,a[++t]=y;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                if(g[i][j]+g[i][k]<g[j][k])
                    g[j][k]=g[i][j]+g[i][k];
    for(i=2;i<=t;i++)
    {
        for(j=0;j<=n;j++) dp[i][j]=1e16;
        x=a[i-1],y=a[i];
        for(j=1;j<=n;j++)
        {
            dp[i][x]=min(dp[i][x],dp[i-1][j]+min(g[x][y],g[j][y]));
            dp[i][j]=min(dp[i][j],dp[i-1][j]+min(g[x][y],g[j][y]));
            for(k=1;k<=n;k++)
                dp[i][k]=min(dp[i][k],min(dp[i-1][j]+g[j][k]+g[k][y],dp[i-1][j]+g[x][k]+g[k][y]));
        }
    }
    for(i=1;i<=n;i++) ans=min(ans,dp[t][i]);
    printf("%lld\n",ans);
    return 0;
}