SRM519 Div2 Medium(600) 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]; }};