// Traffic #include #include #include #include #include #include #include #include using namespace std; /***************************************************************************** * Debug Support *****************************************************************************/ #ifdef _DEBUG #define ASSERT(expr) assert(expr) #else //! _DEBUG #define ASSERT(expr) ((void) 0) #endif//! _DEBUG /***************************************************************************** * Data Type Definitions *****************************************************************************/ /** 座標値 */ typedef int coord; /** 座標 (2-D) */ typedef pair position; /** 方角 */ enum direction { DIR_NORTH = 0, // 北 (y 座標増加方向) DIR_SOUTH = 1, // 南 DIR_EAST = 2, // 東 (x 座標増加方向) DIR_WEST = 3, // 西 NDIRS = 4, }; /** 方向(軸) */ enum axis { VERTICAL = 0, // 南北 HORIZONTAL = 1, // 東西 NAXES = 2, }; /** 各格子点の情報を保持する構造体 */ struct point { /** 座標位置 */ position pos; /** 隣接点へのポインタ */ point *link[NDIRS]; /** 点の種別 */ enum type_t { SIGNAL = 0, // 信号 POINT = 1, // ただの点 (スタート、ゴール) } type; /** 各方向が青になっている時間 (type == SIGNAL の場合のみ) */ int time[NAXES]; /** 時刻 0 における状態 (type == SIGNAL の場合のみ) */ int state; /** * コンストラクタ * * @param pos 座標 * @param type 種別 */ point(position pos, type_t type = SIGNAL) : pos(pos), type(type), state(-1) { // とりあえず zero fill memset(&link, 0, sizeof(link[0]) * NDIRS); memset(&time, 0, sizeof(time[0]) * NAXES); } }; /***************************************************************************** * Operation on Data Structures *****************************************************************************/ /** * 点を挿入する。 * * @param pt 挿入する点 * @param bef 挿入される位置 * @param dir bef から見て pt をどの方向に挿入するか */ static inline void insert(point *pt, point *bef, int dir) { // dir ^ 1 は dir と反対方向を表す。 point *aft = bef->link[dir]; ASSERT(aft != NULL && aft->link[dir ^ 1] == bef); pt->link[dir] = aft; aft->link[dir ^ 1] = pt; bef->link[dir] = pt; pt->link[dir ^ 1] = bef; } /** * 信号の行列に点を挿入する * * @param m 行列 * @param cox 通りの X 座標値 * @param coy 通りの Y 座標値 */ static void matrix_insert(vector >& m, const vector& cox, const vector& coy, point *pt) { ASSERT(m.size() == coy.size() && m[0].size() == cox.size()); #define SEARCH(ax, ax2, ci, cj, ptref, dir) \ do { \ const int _i = find(ci.begin(), ci.end(), pt->pos.ax) - ci.begin(); \ if(_i < ci.size()) { \ int _j = lower_bound(cj.begin(), cj.end(), pt->pos.ax2) - cj.begin(); \ if(cj[_j] == pt->pos.ax2) goto error; /* 交差点とぶつかっている */ \ if(_j == 0 || _j >= cj.size()) ASSERT(false); /* 範囲外 */ \ _j--; point *p = ptref; \ /* 交差点以外の点が入っているかもしれないのでループをまわす */ \ for(; p && p->link[dir]->pos.ax2 < pt->pos.ax2; p = p->link[dir]); \ ASSERT(p != NULL); insert(pt, p, dir); return; \ } \ } while(0) SEARCH(first, second, cox, coy, m[_j][_i], DIR_NORTH); SEARCH(second, first, coy, cox, m[_i][_j], DIR_EAST ); #undef SEARCH error: cerr << "matrix_insert() got an error: inserting (" << pt->pos.first << ", " << pt->pos.second << ")" << endl; assert(false); } /***************************************************************************** * Solve the Problem *****************************************************************************/ /** * 点と点の距離を計算する。 * * @param a 座標 * @param b 座標 * @return 距離 */ static inline int dist(const position& a, const position& b) { // どちらかの軸は一致しているはずなのでマンハッタン距離の式でよい ASSERT(a.first == b.first || a.second == b.second); return abs(a.first - b.first) + abs(a.second - b.second); } /** * 必要に応じて信号待ちをする。 * * @param time 信号に到達した時間 * @param p 信号をあらわす点 * @param dir 通りたい方向 * @return 信号を通過できる時間 (>= time) */ static int wait_signal(int time, const point *p, int dir) { ASSERT(p->type == point::SIGNAL); // 信号の周期、また目的の方向が青になる時間(mod 周期)を求める int period = 0, start = 0, rem = time; for(int i = 0; i < NAXES; i++) period += p->time[i]; for(int i = p->state; ; i = (i + 1) % NAXES) if(i == dir) break; else start += p->time[i]; //Case analysis: const int cur = time % period; if(cur < start) // cur < start (< end) return time + (start - cur); // Here, start <= cur if(cur < start + p->time[dir]) // start <= cur < end (= next) return time; // Here, (start <) end <= cur. Wait for the next round return time + (period + start - cur); } /** * 問題を解く。 * * @param ps スタートの情報 * @param pd ゴールの情報 * @return スタートからゴールまでにかかる最短時間 */ int solve(const point *ps, const point *pd) // Dijkstra { typedef pair state; priority_queue, greater > Q; map arrival; Q.push(make_pair(0, ps)); while(!Q.empty()) { const state s = Q.top(); Q.pop(); #ifdef _DEBUG cerr << "Reached (" << s.second->pos.first << ", " << s.second->pos.second << ")[" << s.second->type << "] at time=" << s.first << endl; #endif//_DEBUG if(s.second == pd) return s.first; if(arrival.count(s.second)) continue; arrival[s.second] = s.first; // 次に行ける点へ展開 const point *cur = s.second; for(int i = 0; i < NDIRS; i++) { const point *nxt = cur->link[i]; if(!nxt || arrival.count(nxt)) continue; // そのポイントへの到着時間を計算する int ntime = s.first + dist(cur->pos, nxt->pos); if(nxt->type == point::SIGNAL) { // 信号待ちを加味 axis ax; if(cur->pos.first == nxt->pos.first) ax = VERTICAL; else if(cur->pos.second == nxt->pos.second) ax = HORIZONTAL; else ASSERT(false); ntime = wait_signal(ntime, nxt, ax); } #ifdef _DEBUG cerr << " -> (" << nxt->pos.first << ", " << nxt->pos.second << ") @ ETA=" << ntime << endl; #endif//_DEBUG Q.push(make_pair(ntime, nxt)); } } // 到達不可能な場合はありえない cerr << "solve() got an error: unreachable goal" << endl; assert(false); } /***************************************************************************** * Bootstrap *****************************************************************************/ int main() { int w, h; while(cin >> w >> h, w || h) { // 座標を読んでくる vector cox, coy; #define READ_COORD(v, sz) \ do { \ v.push_back(0); \ for(int _i = 0, len; _i < (sz) - 1; _i++) \ cin >> len, assert(len >= 2 && len <= 1000), \ v.push_back(v.back() + len); \ ASSERT(v.size() == (sz)); \ } while(0) READ_COORD(cox, w); READ_COORD(coy, h); #undef READ_COORD // マトリクスを作る vector > sigs(h, vector(w)); for(int y = 0; y < h; y++) for(int x = 0; x < w; x++) { sigs[y][x] = new point(position(cox[x], coy[y])); point& p = *sigs[y][x]; cin >> p.time[VERTICAL] >> p.time[HORIZONTAL] >> p.state; assert(p.time[VERTICAL] >= 1 && p.time[VERTICAL] < 100 && p.time[HORIZONTAL] >= 1 && p.time[HORIZONTAL] < 100); assert(p.state == 0 || p.state == 1); } for(int y = 0; y < h; y++) for(int x = 0; x < w; x++) { if(x > 0) sigs[y][x]->link[DIR_WEST] = sigs[y][x - 1]; if(x < w - 1) sigs[y][x]->link[DIR_EAST] = sigs[y][x + 1]; if(y > 0) sigs[y][x]->link[DIR_SOUTH] = sigs[y - 1][x]; if(y < h - 1) sigs[y][x]->link[DIR_NORTH] = sigs[y + 1][x]; } // 出発地点、目的地 position src, dst; cin >> src.first >> src.second >> dst.first >> dst.second; point *ps = new point(src, point::POINT); point *pd = new point(dst, point::POINT); matrix_insert(sigs, cox, coy, ps); matrix_insert(sigs, cox, coy, pd); cout << solve(ps, pd) << endl; // cleanup delete ps; delete pd; for(int y = 0; y < h; y++) for(int x = 0; x < w; x++) delete sigs[y][x]; sigs.clear(); } }