2020 뉴커머스 여름방학 다교훈련캠프(5차전) A.Portal

제목 링크
사고방식: dp[i][j][k]dp[i][j][k]dp[i][j][k]는 첫 번째 임무를 완성하는 것을 의미한다. 현재 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에서 x4.j에서 y로, y에 전송문을 설치하여 k로, k에서 x5.j에서 k로, k에서 y로, y에서 전송문을 설정하고, y에서 x로
Floyd로 최단로를 미리 처리하고 옮기면 됩니다.
수조가 3차원으로 켜진 것은 처음에 비뚤어진 생각을 했기 때문이다.그리고 웨이는 몇 발을 발견했는데 어떤 것은 옮기고 쓰지 않았지만 3차원은 분명히 터질 것이다. 그리고 문득 크게 깨달았다. 어떤 임무를 완수한 후에 나는 반드시 그 임무 노드에 멈출 것이다...

#include 
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<
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->l
    for(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]);//1
        dp[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]);//3
          dp[st][l][y]=min(dp[st][l][y],dp[st^1][j][x]+w[j][y]+w[j][l]);//4
          dp[st][l][y]=min(dp[st][l][y],dp[st^1][j][x]+w[j][y]+w[y][l]);//5
        }
      }
    }
    //          x   ，          0s   x
    st^=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<<'
';
  return 0;
}