原题链接https://ac.nowcoder.com/acm/contest/5670/A

当你查看这篇题解时，作者可能正躺在医院中接受治疗

题目描述

现在你被关在一间有n个顶点m条有长度的边的工厂中，并有k个任务需要你来完成。任务被万恶之源题目描述为按照任务被给出的顺序从顶点图片说明 到顶点图片说明 。
为了方便你完成任务，布置者从Terraria中偷出了拿出了传送门枪和开关并交给你。

  • 传送门枪：在你当前坐标建立传送门；当工厂中有两个传送门时，你可以在传送门所在地之间传送任意次数。
  • 开关：你可以任意关闭一个传送门。
  • 注：工厂中最多有且只有两个传送门；若已有两个传送门，你必须先关闭其中一个传送门才能另外建立传送门。
    传送门枪只能在你当前坐标建立传送门！传送门枪只能在你当前坐标建立传送门！传送门枪只能在你当前坐标建立传送门！
    开关只能关闭传送门！开关只能关闭传送门！开关只能关闭传送门！（重要的事情说三遍）

当然，为了尽早偷懒完成任务，你决定计算最少步数及方案。

输入描述

  • 第一行输入n,m,k三个整数，分别表示有顶点数，边数和任务数；
  • 接下来m行每行输入u,v,w三个整数，分别表示边连接的两个顶点和边的长度；
  • 最后k行每行输入a,b两个整数，分别表示每次任务的起点和终点。
  • 1≤n≤300,1≤m≤40000,1≤k≤300,1图片说明 图片说明 ,图片说明 图片说明 n,0图片说明 图片说明 图片说明 图片说明 ,1图片说明 图片说明 ,图片说明 图片说明 n

其中确保图被连接；

输出描述

仅输出你所需的最小步数。

样例

  1. 样例1

输入
5 4 2
1 2 1
2 3 1
3 4 1
4 5 1
1 5
2 4
输出
5

说明：

作者真的太懒了不想打了，请各位哥哥姐姐点击上方的原题链接看原题说明吧。

  1. 样例2

    输入
    6 10 3
    1 1 6
    5 6 9
    3 5 8
    1 4 1
    2 4 7
    6 6 10
    1 4 2
    6 5 10
    3 5 2
    3 1 9
    1 5
    2 5
    4 3
    输出
    28

  2. 样例3

    输入
    6 10 3
    1 1 3
    3 1 1
    6 2 3
    1 6 10
    4 1 1
    3 1 2
    5 6 9
    5 4 10
    6 3 4
    3 4 4
    3 5
    3 6
    6 5
    输出
    16

题解思路

你以为题目很麻烦，但其实它只要经过2k个点。
所以DP转移即可。
但显然（既然显然为什么我要打。。。），暴力转移会明显爆，况且在这个DP转移中可能存在环。
所以我们才需要Dijkstra。
其实，这题Floyd并不会炸（简直运气好得一批），只不过稍微麻烦那么亿一点点。
传送门的存在确实是个坑。。。。吗？
你明明可以只记录其中一个，并随时创造一个传送门。如此看来，记录当前所在位置也变得不那么重要了。

DP转移方程懒得打了。。。藏在了代码里，可以自由参考。。。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long c[700];
long long ans=1e18+7;
long long dp[700][700];
long long dis[400][400],w[400][400];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++) dis[i][j]=1e18+7;
        dis[i][i]=0;
    }
    long long x,y,z;
    for (int i=1; i<=m; i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        dis[x][y]=dis[y][x]=min(dis[x][y],z);
    }
    for (int i=1; i<=k; i++)
    {
        scanf("%lld%lld",&x,&y);
        c[i*2]=y;
        c[i*2-1]=x;
    }
    for(int v=1; v<=n; v++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                dis[i][j]=min(dis[i][j],dis[i][v]+dis[v][j]);
    for (int i=0; i<=2*k; i++)
        for (int j=0; j<=n; j++)
        dp[i][j]=1e18+7;
    c[0]=1;
    dp[0][1]=0;
    for(int i=0; i<2*k; i++)
        for(int j=1; j<=n; j++)
        {
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+dis[c[i]][c[i+1]]);
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+dis[j][c[i+1]]);
            for(int l=1; l<=n; l++)
                dp[i+1][l]=min(dp[i+1][l],dp[i][j]+min(dis[c[i]][l],dis[j][l])+min(dis[j][c[i+1]],dis[l][c[i+1]]));

        }
    for(int i=1; i<=n; i++)
        ans=min(ans,dp[2*k][i]);
    printf("%lld",ans);
}

求三连鸭 ~（不好意思走错场了）