ABC286 E問題 Souvenir

グラフの最短経路

問題：有向グラフの最短＋頂点の重みの和の最大経路を求める

グラフの最短経路を求める代表的なアルゴリズムには次の3つのアルゴリズムがあります。

ダイクストラ法 (特定の始点から全頂点, 辺の重みが負でない)
ベルマン–フォード法 (特定の始点から全頂点, 辺の重みが負でもよい)
ワーシャル–フロイド法 (全頂点ペアの間)

ここでは、複数の頂点ペアについて質問されるので、全ペアの最短経路を求めるワーシャル–フロイド法を使います。

ワーシャル–フロイド法のアイデアは、
「頂点 p = 1,2,...,k-1 を経由してもよいという条件のもとで頂点 i ⇒ j へ移動する最短経路 d[i][j] が全(i,j) ペアについて求められているとします。
ここに頂点 k を経由してもよいという条件を追加すると、最短経路は d[i][j] か d[i][k]+d[k][j] の小さいほうになります。
この k を 1から N まで増やせば最終的な最短経路 d[i][j] が求められます。」
というものです。

辺の重みを決める

経由する辺の数が最小
経由する辺の数が同数の場合、通過する頂点の重みが最大

このような経路を求めたい。

問題では頂点に重みがつけられていますが、「頂点 i ⇒ 頂点 j の辺に対して頂点 j の重みを割り当てる」という辺の重みを採用すれば、
全経路の辺の重みの総和にスタート頂点の重みを加えることで、通る頂点の重みの総和と同じになります。

最短経路の探索のアルゴリズムなので、「重みの最大」ではなく、「重みの -1 倍の最小」を見つけることにします。

また、辺の数が最小であることが優先になりますが、辺の重みを「(定数)-(移動先の頂点の重み)」として、この定数を全頂点の重みの和より大きくすれば、
辺の数が多いほうが必ず辺の重みの和が大きくなり、条件を満たす探索ができます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  # 入力データ
  N = readInt()
  A = readInts()

  edge = sum(A) + 1     #  都市の重みの総和よりも大きな値
  inf  = edge * (N+1)   #  経路が無いことを表す定数

  d = Matrix{Int64}(undef,N,N)


  # 各辺の重みを設定

  for i = 1:N
    S = readline()
    for j = 1:N
      if S[j] == 'Y'
        d[i,j] = edge - A[j]   # 辺の重み
      else
        d[i,j] = inf
      end
    end
  end


  # ワーシャル-フロイド法

  for k = 1:N
    for i = 1:N
      for j = 1:N
        if d[i,j] > d[i,k] + d[k,j]
          d[i,j] = d[i,k] + d[k,j]
        end
      end
    end
  end

  # クエリー処理

  Q = readInt()
  for i = 1:Q
    U,V = readInts()

    if d[U,V] == inf
      println("Impossible")
    else
      city = cld(d[U,V] , edge)
      ans = edge * city - d[U,V] + A[U]  # スタート都市の重みを加算する。
      println(city, " ", ans)
    end
  end

end  # function solve


# main
solve()