SRM626D1Med NegativeGraphDiv1

• July 28, 2016
• TopCoder, Educational

これは教育的

問題概要(原文)

$N$ 頂点 $M$ 本の重みつき有向辺からなるグラフがある． $0$ から $N-1$ への最短路を求めよ．ただし， $K$ 回までは，辺のコストを $-1$ 倍した値として扱うことができる．

考察

基本的には最短路問題なことはわかる． 辺のコストを $-1$ 倍した回数が $1,2,4,8, \ldots, 2^k$ 回以内のときの $s \rightarrow t$ 最短路を求めよう． これはワーシャルフロイド法を用いて $O(N^2 M + N^3logK)$ でできる． あとは， 繰り返し二乗法の要領で， $0 \rightarrow 1$ 最短路を求めればよい．

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class NegativeGraphDiv1
{
    public long findMin(int n, int[] from, int[] to, int[] weight, int charges)
    {
        var m = from.Length;
        const long INF = 1L << 60;
        var g = Enumerate(n, x => new long[n]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = i != j ? INF : 0;

        for (int i = 0; i < m; i++)
        {
            from[i]--; to[i]--;
            g[from[i]][to[i]] = Math.Min(g[from[i]][to[i]], weight[i]);
            //Debug.WriteLine("{0} {1} {2}", from[i], to[i], weight[i]);
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    g[i][j] = Math.Min(g[i][j], g[i][k] + g[k][j]);


        var d = Enumerate(35, x => Enumerate(n, y => new long[n]));
        for (int k = 0; k < 35; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    d[k][i][j] = INF;
        for (int i = 0; i < m; i++)
        {
            for (int f = 0; f < n; f++)
                for (int t = 0; t < n; t++)
                    d[0][f][t] = Math.Min(d[0][f][t], Math.Min(g[f][t], g[f][from[i]] + g[to[i]][t] - weight[i]));
        }
        for (int k = 1; k < 35; k++)
        {
            for (int t = 0; t < n; t++)
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        d[k][i][j] = Math.Min(d[k][i][j], d[k - 1][i][t] + d[k - 1][t][j]);

        }
        for (int t = 0; t < 35; t++, charges /= 2)
        {
            if ((charges & 1) == 0) continue;
            var next = Enumerate(n, x => new long[n]);
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    next[i][j] = INF;
            for (int k = 0; k < n; k++)
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        next[i][j] = Math.Min(next[i][j], g[i][k] + d[t][k][j]);
            g = next;
        }

        return g[0][n - 1];
    }

    static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }

}

コメント

• 繰り返し二乗法に気づけば簡単

• graph
• matrix

• Twitter
•