题目链接

思路：$dp[i][j][k]$表示完成第i个任务，当前在j节点，有一个传送门在k节点的最小花费。
显然 ，完成第i个任务后，j在目标节点上是最优的。。。。
分以下几种情况分类转移，设当前目标节点为x：
1.j->x 。j直接走到x。
2.j->k->x 。在j设置传送门，传送到k，从k走到x，此时可以选择关闭j/k的任意一个传送门。
3.从j走到y，在y设置传送门，从y走到x
4.从j走到y，在y设置传送门，传送到k，从k走到x
5.从j传送到k，从k走到y，在y设置传送门，从y走到x

用Floyd预处理一下最短路，然后转移即可。。

数组开三维是因为，一开始想歪了。。然后wa了几发发现，有种转移没写，但是三维明显会炸，然后恍然大悟，发现完成某一次任务后，我必然会停在那个任务节点.。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e2 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
LL w[N][N];
int n,m,k;
LL dp[2][N][N];//表示 在 i 位置  传送们 在 j位置 的最短路程
LL mn[N];
int L[N*3];
int main() {ios::sync_with_stdio(false);cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)w[i][j]=0;else w[i][j]=4e14;dp[0][i][j]=dp[1][i][j]=1e18;}}for(int i=1;i<=m;i++){int x,y;LL z;cin>>x>>y>>z;w[x][y]=min(w[x][y],z);w[y][x]=min(w[y][x],z);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int x=1;x<=n;x++){w[j][x]=min(w[j][x],w[j][i]+w[i][x]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[0][i][j]=min(w[1][i]+w[i][j],w[1][j]+w[j][i]);}}int st=1;L[0]=1;for(int i=1;i<=k;i++)cin>>L[2*i-1]>>L[2*i];for(int i=1;i<=2*k;i++){int l=L[i];//j->l//j->x->l//j->y->lfor(int j=L[i-1];j<=L[i-1];j++){for(int x=1;x<=n;x++){dp[st][l][x]=min(dp[st][l][x],dp[st^1][j][x]+w[j][l]);//1dp[st][l][x]=min(dp[st][l][x],dp[st^1][j][x]+w[x][l]);//2 dp[st][l][j]=min(dp[st][l][j],dp[st^1][j][x]+w[x][l]);mn[j]=min(mn[j],dp[st^1][j][x]);for(int y=1;y<=n;y++){dp[st][l][y]=min(dp[st][l][y],dp[st^1][j][x]+w[x][y]+w[y][l]);//3dp[st][l][y]=min(dp[st][l][y],dp[st^1][j][x]+w[j][y]+w[j][l]);//4dp[st][l][y]=min(dp[st][l][y],dp[st^1][j][x]+w[j][y]+w[y][l]);//5}}}//有一个 传送门 在 x 的话，无论我在哪里 我都能0s到达 xst^=1;for(int j=1;j<=n;j++){for(int x=1;x<=n;x++){dp[st][j][x]=1e18;}}}LL ans=1e18;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans=min(ans,dp[st^1][i][j]);}}cout<<ans<<'\n';return 0;
}