概要

V マスへの通常移動だけコストが重く（2分）、さらに同じ地下水路内なら 0 分移動できる、という「重み付き最短路」問題です。
V の連結成分を1つの「中継ノード」にまとめたグラフを作り、ダイクストラ法で最短時間を求めます。

考察

この問題の難しさは、V に関する2種類の移動が混在している点です。

• 通常移動で V に入る：\(1 + 1 = 2\) 分
• V 上にいるとき、同じ地下水路内の任意 V へ：\(0\) 分

重要な気づき1：地下水路内の 0 分移動は「連結成分単位」で扱える

同じ地下水路（V の連結成分）内なら、どの V 同士も実質 0 分で行き来できます。
そこで、各連結成分に対して スーパー頂点を1つ作り、

• V マス → 成分頂点（0）
• 成分頂点 → V マス（0）

という辺を張ると、成分内ワープを自然に表現できます。

これにより、「同じ成分内の全 V 同士に 0 コスト辺を張る」必要がなくなり、辺数爆発を防げます。

重要な気づき2：通常移動は「移動先の種類」でコストが決まる

問題文より、上下左右の通常移動は基本1分で、移動先が V なら追加1分です。
よって通常移動の重みは

• 移動先が V：2
• それ以外（S,G,O）：1

となります（X はそもそも通れない）。

素朴解法が厳しい理由

• 各 V から同成分内すべてへ 0 コスト辺を張ると、最悪で二乗オーダーの辺数になりTLE/MLEの危険。
• BFSでは重み 0/1/2 が混在するためそのまま使えません（0-1 BFSも2があるので不可）。

したがって、
1. V 連結成分を作る
2. スーパー頂点化してグラフを疎に保つ
3. ダイクストラ法
が自然な方針です。

アルゴリズム

1. 前処理：V の連結成分IDを振る

   • グリッド全体を見て、未訪問の V から BFS（またはDFS）で同成分を塗る。
   • comp_id[cell] に成分番号を記録。

2. 拡張グラフを構築

   • 通常マス頂点：\(0 \ldots N-1\)（\(N=H \times W\)）
   • 成分スーパー頂点：\(N \ldots N+C-1\)（\(C\) は V 成分数）
   • 通行可能マス u から隣接通行可能マス v へ通常移動辺を追加：
     • 重み \(2\)（v が V）
     • 重み \(1\)（それ以外）
   • u が V なら
     • u -> super(comp_id[u]) に重み0
     • super(comp_id[u]) -> u に重み0

3. ダイクストラ法

   • 始点 S から最短距離を計算。
   • G の距離が更新されなければ到達不可で NO、そうでなければその値を出力。

計算量

• 時間計算量: \(O((N + E)\log(N+C))\)
  ここで \(N=H\times W\)。
  隣接辺は各マス高々4本なので \(E=O(N)\)、また V と成分頂点の0辺も合計 \(O(N)\)。
  よって全体として \(O(N\log N)\) 程度。
• 空間計算量: \(O(N + E)=O(N)\)

実装のポイント

• マス \((r,c)\) を1次元ID r*W+c に変換すると実装しやすいです。

• passable(ch) = (ch != 'X') で通行判定を統一するとバグを減らせます。

• 通常移動コストは「現在地」ではなく移動先で決まる点に注意。

• ダイクストラでは if d != dist[u]: continue を入れて、古いヒープ要素を無視します。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    grid = [input().strip() for _ in range(H)]
    N = H * W

    def idx(r, c):
        return r * W + c

    start = goal = -1
    for r in range(H):
        row = grid[r]
        for c, ch in enumerate(row):
            if ch == 'S':
                start = idx(r, c)
            elif ch == 'G':
                goal = idx(r, c)

    # 1) Label connected components of V-cells
    comp_id = [-1] * N
    comp_count = 0
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for r in range(H):
        for c in range(W):
            if grid[r][c] != 'V':
                continue
            i0 = idx(r, c)
            if comp_id[i0] != -1:
                continue
            cid = comp_count
            comp_count += 1
            q = deque([i0])
            comp_id[i0] = cid
            while q:
                v = q.popleft()
                vr, vc = divmod(v, W)
                for dr, dc in dirs:
                    nr, nc = vr + dr, vc + dc
                    if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] == 'V':
                        ni = idx(nr, nc)
                        if comp_id[ni] == -1:
                            comp_id[ni] = cid
                            q.append(ni)

    # 2) Build super graph:
    # node 0..N-1 : cells
    # node N..N+comp_count-1 : component supernodes
    total_nodes = N + comp_count
    adj = [[] for _ in range(total_nodes)]

    def passable(ch):
        return ch != 'X'

    for r in range(H):
        for c in range(W):
            ch = grid[r][c]
            if not passable(ch):
                continue
            u = idx(r, c)

            # normal moves to neighbors
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < H and 0 <= nc < W:
                    nch = grid[nr][nc]
                    if passable(nch):
                        v = idx(nr, nc)
                        w = 2 if nch == 'V' else 1
                        adj[u].append((v, w))

            # zero-cost teleport via V component
            if ch == 'V':
                cid = comp_id[u]
                snode = N + cid
                adj[u].append((snode, 0))
                adj[snode].append((u, 0))

    # 3) Dijkstra
    INF = 10**30
    dist = [INF] * total_nodes
    dist[start] = 0
    import heapq
    hq = [(0, start)]

    while hq:
        d, u = heapq.heappop(hq)
        if d != dist[u]:
            continue
        if u == goal:
            break
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))

    ans = dist[goal]
    if ans >= INF:
        print("NO")
    else:
        print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。