読者です 読者をやめる 読者になる 読者になる

SRM 519 Div2 Medium ThreeTeleports

問題

(xMe, yMe)から(xHome, yHome)へ移動したい.隣接する点には1秒で移動できる.指定された2点間はテレポートを行い10秒で移動することも出来る.(xMe, yMe)から(xHome, yHome)へ移動するときの最小の時間を求めよ.

解答

(xMe, yMe),(xHome, yHome),テレポート出来る点を頂点とし,各頂点間の最短距離を求める.

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}

class ThreeTeleports
{
public:
  int shortestDistance(int xMe, int yMe, int xHome, int yHome, vector <string> teleports)
    {
      typedef pair<long long, long long> point;
      point start(xMe, yMe);
      point end(xHome, yHome);
      set<point> ps;
      ps.insert(start);
      ps.insert(end);
      map<pair<point, point>, long long> M;
      map<pair<point, point>, bool> teleport;
      for(int i = 0; i<(int)teleports.size(); i++){
        vector<int> x(4, 0);
        // sscanf(teleports[i].c_str(), "%d", &(x[3]));
        sscanf(teleports[i].c_str(), "%d %d %d %d", &(x[0]), &(x[1]), &(x[2]), &(x[3]));
        // for(int j = 0; j < 4; j++){
        //   cin >> x[j];
        // }
        point p1(x[0], x[1]);
        point p2(x[2], x[3]);
        ps.insert(p1);
        ps.insert(p2);
        teleport[make_pair(p1,p2)] = true;
        teleport[make_pair(p2,p1)] = true;
      }
      set<point>::iterator itr1, itr2, itr3;
      for(itr1 = ps.begin(); itr1 != ps.end(); itr1++){
      for(itr2 = ps.begin(); itr2 != ps.end(); itr2++){
        point p1 = *itr1;
        point p2 = *itr2;
        M[make_pair(p1, p2)] = abs(p1.first-p2.first) + abs(p1.second-p2.second);
        if (teleport[make_pair(p1, p2)] && M[make_pair(p1, p2)] > 10){
          M[make_pair(p1, p2)] = 10;
        }
      }
      }
      for(itr1 = ps.begin(); itr1 != ps.end(); itr1++){
      for(itr2 = ps.begin(); itr2 != ps.end(); itr2++){
      for(itr3 = ps.begin(); itr3 != ps.end(); itr3++){
        point p1 = *itr1;
        point p2 = *itr2;
        point p3 = *itr3;
        M[make_pair(p2, p3)] = min(M[make_pair(p2, p3)],
                                   M[make_pair(p2, p1)] + M[make_pair(p1, p3)]);
        if (M[make_pair(p1, p2)] < 0){
          cout << M[make_pair(p1, p2)] << endl;
        }
      }
      }
      }
      return M[make_pair(start, end)];
    }
};