SRM492 Div1 Medium(550) TimeTravellingTour

TimeTravellingTour

A→B→C→D―(タイムマシン)→B→E という移動はBの時点でCとEに分岐して調査すると考える。都市iから開始してcities[j..k]を調査するコストをc[i][j][k]とすると
c[i][j][k] = min( {c[l][i][k]+road[i][j][k]}∪{c[i][j][m]+c[i][m+1][k]} )。
ただし、lはiと繋がっている都市、j≦m＜k。

#include <string>
#include <vector>
#include <numeric>
#include <sstream>
using namespace std;

class TimeTravellingTour{public:
long long determineCost( int N, vector <int> cities, vector <string> roads )
{
    long long INF = 0x100000000000000ll;

    //  [i][j] 都市iと都市jの間のコスト
    static long long road[64][64];
    for ( int i=0; i<64*64; i++ )
        road[0][i] = INF;
    string s = accumulate( roads.begin(), roads.end(), string() );
    stringstream ss(s);
    int a, b, c;  char t;
    while ( ss>>a>>t>>b>>t>>c )
        road[a][b] = road[b][a] = c;

    //  [i][j][k]　都市iから開始して、cities[j..k]の都市を調査する最小コスト
    static long long cost[64][64][64];
    for ( int i=0; i<64*64*64; i++ )
        cost[0][0][i] = INF;
    
    int M = (int)cities.size();
    
    for ( int w=0; w<M; w++ )
    for ( int c1=0; c1+w<M; c1++ )
    {
        int c2 = c1 + w;

        //  都市にいれば調査可能
        if ( w == 0 )
            cost[cities[c1]][c1][c2] = 0;            

        //  タイムマシン
        for ( int i=0; i<N; i++ )
        for ( int j=c1; j<c2; j++ )
            cost[i][c1][c2] = min( cost[i][c1][c2],
                                   cost[i][c1][j]+cost[i][j+1][c2] );

        //  道路
        bool up;
        do
        {
            up = false;

            for ( int i=0; i<N; i++ )
            for ( int j=0; j<N; j++ )
                if ( cost[i][c1][c2] > cost[j][c1][c2]+road[i][j] )
                    cost[i][c1][c2] = cost[j][c1][c2]+road[i][j],
                    up = true;
        }
        while ( up );
    }

    return cost[0][0][M-1]<INF ? cost[0][0][M-1] : -1;
}};