UVA 1078 Steam Roller：狀態擴展最短路 (方向+轉彎標記)

UVA 1078 Steam Roller：狀態擴展最短路 (方向+轉彎標記)

網格地圖，從起點達到終點最短時間。進入轉彎格子時，進出時間加倍。建模狀態 (x, y, dir, turned)：位置、進入方向、是否已經為此轉彎加倍。

狀態定義

• dir ∈ {0,1,2,3}：上左下右 (進入該格的方向)。
• turned ∈ {0,1}：是否已經支付了該格的轉彎額外代價。
• 起點虛擬節點 0，連向起點四鄰格，代價 = 邊權 × 2 (起點視為轉彎)。
• 轉移：從 (x,y,dir1,turned) 移動到鄰格 (nx,ny) 方向 dir2。
  • 若 dir1 == dir2 (直行)：代價 = 邊權，turned' = 0 (新格未轉彎)。
  • 若 dir1 != dir2 (轉彎)：
    • turned=0：代價 = 進入邊權 + 轉彎額外代價 (即 grid[x][y][3-dir1]) + 出去邊權，turned' = 1。
    • turned=1：代價 = 邊權 (已支付過)，turned' = 1。

Dijkstra 實現要點

• 節點總數 ≤ R×C×4×2 ≤ 100×100×8 = 80,000，邊數約 4 倍，堆優化 Dijkstra 極快。
• 用 id[x][y][dir][turned] 動態分配節點編號。
• 邊權為整數，INF = 0x3f3f3f3f。

核心代碼結構

struct Edge { int u, v, w; };
// 標準 Dijkstra 模板 ...

int get_id(int x, int y, int d, int f) {
    if (id[x][y][d][f] == -1) id[x][y][d][f] = gao.n++;
    return id[x][y][d][f];
}

void build_edges() {
    // 起點虛擬節點 0
    for (int d = 0; d < 4; d++)
        if (can(r1,c1,d))
            gao.add_edge(0, get_id(r1+dx[d], c1+dy[d], d, 1), grid[r1][c1][d]*2);
    // 普通轉移
    for (int x=0;x