AOJ 2200 Mr.Rito Post Office

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf=(ll)1e14;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
  int n,m;
  while(cin>>n>>m,n){
    ll land[201][201],sea[201][201];
    int a[1001];
    for(int i=0;i<201;i++){
      for(int j=0;j<201;j++){
        land[i][j]=inf;
        sea[i][j]=inf;
      }
    }
    for(int i=0;i<201;i++){
      land[i][i]=0;
      sea[i][i]=0;
    }
    for(int i=0;i<m;i++){
      int x,y;ll t;
      char sl;
      cin>>x>>y>>t>>sl;
      x--;y--;
      if(sl=='S'){
        sea[x][y]=t;
        sea[y][x]=t;
      }else{
        land[x][y]=t;
        land[y][x]=t;
      }
    }
    int r;cin>>r;
    for(int i=0;i<r;i++){
      cin>>a[i];a[i]--;
    }
    for(int k=0;k<n;k++){
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
          sea[i][j]=min(sea[i][j],sea[i][k]+sea[k][j]);
          land[i][j]=min(land[i][j],land[i][k]+land[k][j]);
        }
      }
    }
    ll dp[1001][201];
    for(int i=0;i<r;i++)for(int j=0;j<n;j++)dp[i][j]=inf;
    dp[0][a[0]]=0;
    for(int i=0;i<r-1;i++){
      for(int j=0;j<n;j++){
        if(dp[i][j]==inf)continue;
        for(int k=0;k<n;k++){
          dp[i+1][k]=min(dp[i+1][k],dp[i][j]+land[a[i]][j]+sea[j][k]+land[k][a[i+1]]);
          if(j==k){
            dp[i+1][k]=min(dp[i+1][k],dp[i][j]+land[a[i]][a[i+1]]);
          }
        }
      }
    }
    /*for(int i=0;i<r;i++){
      for(int j=0;j<n;j++){
        cout<<dp[i][j]<<" ";
      }
      cout<<endl;
    }
    cout<<endl;*/
    ll ans=inf;
    for(int i=0;i<n;i++){
      ans=min(ans,dp[r-1][i]);
    }
    cout<<ans<<endl;
  }
  return 0;
}

• 解いたの2回目なのにある所でずっと躓いていた。
• 反省点 必ずしもdp[i][k]+dp[k][j]= dp[i][j]ではないということ。
• これを意識すればチョロかった。