SRM519 Div2 Medium(600) ThreeTeleports

ThreeTeleports

現在地・家の位置・テレポートの端点をグラフの頂点とし、マンハッタン距離を辺の重みとする。ただしテレポートの間は10とマンハッタン距離の小さい方。とすると、グラフの最短経路問題になる。頂点数が8しかないので、ダイクストラでなくてもOK。

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

class ThreeTeleports{public:
int shortestDistance( int xMe, int yMe, int xHome, int yHome, vector <string> teleports )
{
    //  0: Me
    //  1: Home
    //  2,3: teleport 1
    //  4,5: teleport 2
    //  6,7: teleport 3
    int x[8], y[8];
    x[0]=xMe, y[0]=yMe;
    x[1]=xHome, y[1]=yHome;
    for ( int i=0; i<3; i++ )
    {
        stringstream ss(teleports[i]);
        ss>>x[i*2+2]>>y[i*2+2]>>x[i*2+3]>>y[i*2+3];
    }

    long long d[8][8];
    for ( int i=0; i<8; i++ )
    for ( int j=0; j<8; j++ )
        d[i][j] = abs(x[i]-x[j])+abs(y[i]-y[j]);
    for ( int i=0; i<3; i++ )
        d[i*2+2][i*2+3] = min( d[i*2+2][i*2+3], 10ll ),
        d[i*2+3][i*2+2] = min( d[i*2+3][i*2+2], 10ll );

    for ( int i=0; i<8; i++ )
    for ( int j=0; j<8; j++ )
    for ( int k=0; k<8; k++ )
        d[j][k] = min( d[j][k], d[j][i]+d[i][k] );

    return (int)d[0][1];
}};