SRM652D1Med MaliciousPath

これクッソ教育的

問題概要(原文)

$N$ 頂点 $M$ 本の重み付きの有向辺があるグラフがある.

$A$ くんは初め頂点 $1$ にいて,頂点 $N$ にいきたい. $A$ くんが辺 $e$ を選んだあと, $A$ くんはその辺 $e$ にそって移動する. $A$ くんが辺を選んだ直後のタイミングで, $B$ くんはその辺 $e$ を別の辺 $e^\prime$ に変えることができる.この操作は $K$ 回までできる.

$B$ くんは $A$ くんが頂点 $N$ につく時刻を遅くしたい. $A$ くんは $A$ くんが頂点 $N$ につく時刻を短くしたい.

このような状況で $A$ くんと $B$ くんが最適に行動したときの $A$ くんが $N$ につく最短時刻を求めよ.不可能ならば $-1$ を返せ.

考察

$B$ くんがどの辺に移動させると最も遅くなるか, $A$ くんがどの辺に移動しようとすると最も早くつけるか,が分からないので難しい.

最後の状況から逆戻しに考える. 即ち, $A$ くんは自由に辺を選んで(元々の辺の向きの逆向きに)移動できる.

ここで, $A$ 君が頂点 $u$ にいて, $B$ 君が操作可能な残り回数を $k$ としたときに,ここから $N$ につくまでにかかる時間の最小値を $dp(u,k)$ とおく. また, $worst(u,k) = max(dp(v,k-1)+w)$ とおく($v$ は辺の行き先, $w$ は辺の重み) とする,

$dp(u,k) = min (max(worst(u,k-1),dp(v,k)+w))$ という遷移を解けばよい.

このままだとループして解けなさそうに見えるが, $dp(u,k)$ が最小の $u$ から順に埋めていけばよい(つまり貰う形ではなく配る形にする).

すると $dp(N,0)$ から始めて, $dp(v,0)$ を埋めたあと, $dp(N,1)$ から始めて…とやっていけばよい.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using StringBuilder = System.Text.StringBuilder;
public class MaliciousPath
{
    public long minPath(int n, int k, int[] from, int[] to, int[] cost)
    {
        var G = Enumerate(n, x => new List<KeyValuePair<int, long>>());
        var RG = Enumerate(n, x => new List<KeyValuePair<int, long>>());
        for (int i = 0; i < from.Length; i++)
        {
            if (from[i] == n - 1) continue;
            G[from[i]].Add(new KeyValuePair<int, long>(to[i], cost[i]));
            RG[to[i]].Add(new KeyValuePair<int, long>(from[i], cost[i]));
        }
        var dp = new long[n];
        for (int i = 0; i < n; i++)
            dp[i] = 1L << 60;
        for (int t = 0; t <= k; t++)
        {
            var next = new long[n];
            for (int i = 0; i < n; i++)
                foreach (var e in G[i])
                    next[i] = Math.Max(next[i], dp[e.Key] + e.Value);
            var d = new long[n];
            for (int i = 0; i < n; i++)
                d[i] = 1L << 60;
            var pq = new PriorityQueue<KeyValuePair<int, long>>((l, r) => l.Value.CompareTo(r.Value));
            pq.Enqueue(new KeyValuePair<int, long>(n - 1, d[n - 1] = 0));
            while (pq.Any())
            {
                var p = pq.Dequeue();
                var pos = p.Key;
                var val = p.Value;
                //System.Diagnostics.Debug.WriteLine("{0} {1}", pos, val);
                if (d[pos] < val)
                    continue;
                if (t > 0)
                    val = Math.Max(next[pos], val);
                next[pos] = val;
                foreach (var e in RG[pos])
                    if (d[e.Key] > val + e.Value) pq.Enqueue(new KeyValuePair<int, long>(e.Key, d[e.Key] = val + e.Value));

            }
            dp = next;
        }
        if (dp[0] >= 1L << 60)
            return -1;
        return dp[0];

    }
    static 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; }

}

#region PriorityQueue and PairingHeap
public class PriorityQueue<T>
{
    PairingHeap<T> top;
    Comparison<T> compare;
    int size;
    public int Count { get { return size; } }
    public PriorityQueue() : this(Comparer<T>.Default) { }
    public PriorityQueue(Comparison<T> comparison) { compare = comparison; }
    public PriorityQueue(IComparer<T> comparer) { compare = comparer.Compare; }
    public void Enqueue(T item)
    {
        var heap = new PairingHeap<T>(item);
        top = PairingHeap<T>.Merge(top, heap, compare);
        size++;
    }
    public T Dequeue()
    {
        var ret = top.Key;
        size--;
        top = PairingHeap<T>.Pop(top, compare);
        return ret;
    }
    public bool Any() { return size > 0; }
    public T Peek() { return top.Key; }
}

#region PairingHeap
public class PairingHeap<T>
{
    public PairingHeap(T k) { key = k; }
    private readonly T key;
    public T Key { get { return key; } }
    private PairingHeap<T> head;
    private PairingHeap<T> next;
    static public PairingHeap<T> Pop(PairingHeap<T> s, Comparison<T> compare)
    {
        return MergeLst(s.head, compare);
    }
    static public PairingHeap<T> Merge(PairingHeap<T> l, PairingHeap<T> r, Comparison<T> compare)
    {
        if (l == null || r == null) return l == null ? r : l;
        if (compare(l.key, r.key) > 0) Swap(ref l, ref r);
        r.next = l.head;
        l.head = r;
        return l;
    }
    static public PairingHeap<T> MergeLst(PairingHeap<T> s, Comparison<T> compare)
    {
        var n = new PairingHeap<T>(default(T));
        while (s != null)
        {
            PairingHeap<T> a = s, b = null;
            s = s.next; a.next = null;
            if (s != null) { b = s; s = s.next; b.next = null; }
            a = Merge(a, b, compare); a.next = n.next;
            n.next = a;
        }
        while (n.next != null)
        {
            var j = n.next;
            n.next = n.next.next;
            s = Merge(j, s, compare);
        }
        return s;
    }
    static void Swap(ref PairingHeap<T> l, ref PairingHeap<T> r) { var t = l; l = r; r = t; }
}
#endregion
#endregion

コメント

  • ダイクストラ法の本質は,キューから出てきた時点で最短距離が確定している,ということ