Portal
您现在在一家大工厂里。可以将工厂看作为具有n个顶点和m个边的图。每个边都有其长度。您有k个任务要做。第i个任务为达顶点a_i，拾取一个块，然后将其发送到顶点b_i。您应该按照从1号到k号的顺序完成任务。最初，您站在顶点1。
你手里拿着枪。当您处于某个顶点u时，您可以向地面射击，然后将在顶点u建立一个传送门。当工厂中有两个传送门时，假设它们分别位于u和v处，则可以在u和v之间进行瞬间转移（就像连接长度为0的u和v的边一样）。
您的手边还有一个遥控器。它使您可以随时随地关闭传送门（一次关闭一个传送门，而不是一次关闭所有传送门）。并且，最多可以有两个现有传送门。因此，如果要在存在两个传送门时创建另一个传送门，则必须先使用控制器将其关闭，然后再创建。您需要找到必须步行的最小距离才能完成所有k个任务。

动态规划。dp[i][j] i表示是第i组任务，j表示传送门的位置

#include<bits/stdc++.h>
using namespace std;
long long dp[800][500],f[800][500],t[10050];
int main (){
long long n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=0;i<=700;++i) for(int j=1;j<=400;++j) dp[i][j]=1ll<<60,f[i][j]=1ll<<60;
for(int i=1;i<=n;++i) f[i][i]=0;
for(long long i=1;i<=m;++i){
    long long x,y,z;
    scanf("%lld%lld%lld",&x,&y,&z);
    f[x][y]=f[y][x]=min(f[x][y],z);
}
int cnt=0;

for(long long k=1;k<=n;++k)for(long long i=1;i<=n;++i)for(long long j=1;j<=n;++j)f[i][j]=min(f[i][k]+f[k][j],f[i][j]);//folyd 求最短路

for(long long i=1;i<=k;++i){
    long long ta,tt;
    scanf("%lld%lld",&ta,&tt);//建造任务
    t[++cnt]=ta; t[++cnt]=tt;
}
dp[0][1]=0;//超级任务
k*=2;
t[0]=1;
for(long long i=1;i<=k;++i){
    for(long long j=1;j<=n;++j){
        dp[i][j]=min(dp[i][j],dp[i-1][j]+f[t[i-1]][t[i]]);//直接从c[i]走到c[i+1]

        for(long long l=1;l<=n;++l){
            dp[i][j]=min(dp[i][j],dp[i-1][l]+f[l][t[i]]+f[t[i-1]][j]);//第二种转移是从c[i]走到q，在q设置传送门，从q传送到p，再从p走到c[i+1]
            dp[i][l]=min(dp[i][l],dp[i-1][j]+f[j][l]+f[l][t[i]]);//第三种转移是从c[i]传送到p，从p走到q，在q设置传送门，最后从q走到c[i+1]

        }
    }
}
long long ans=1ll<<60;
for(long long i=1;i<=n;++i) ans=min(ans,dp[k][i]);
cout<<ans<<endl;

}