結果

問題 No.3312 Fire Engine
コンテスト
ユーザー tobisatis
提出日時 2025-10-24 22:51:00
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 267 ms / 2,000 ms
コード長 1,507 bytes
コンパイル時間 7,212 ms
コンパイル使用メモリ 170,440 KB
実行使用メモリ 197,660 KB
最終ジャッジ日時 2025-10-24 22:51:30
合計ジャッジ時間 15,293 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (96 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
string String()
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return _input[_iter++];
}
T I<T>() where T : IParsable<T> => T.Parse(String(), null);
#endregion

var n = I<int>();
var d = new int[n, n];
for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) d[i, j] = I<int>();
var m = n.ToFlag();
var dp = new long[m, n];
var max = long.MaxValue / 8;
for (var i = 0; i < m; i++) for (var j = 0; j < n; j++) dp[i, j] = max;
dp[1, 0] = 0;
for (var s = 1; s < m; s++)
{
    for (var i = 0; i < n; i++)
    {
        for (var j = 0; j < n; j++)
        {
            if (s.OfFlag(j)) continue;
            var ns = s.WithFlag(j, true);
            dp[ns, j] = Math.Min(dp[ns, j], dp[s, i] + d[i, j] * (n - int.PopCount(s)));
        }
    }
}
var ans = max;
for (var i = 0; i < n; i++) ans = Math.Min(dp[m - 1, i], ans);
Console.WriteLine(ans);

static class BitExtensions
{
    public static int ToFlag(this int i)
    {
        if (i < 0 || 31 <= i) throw new IndexOutOfRangeException();
        return 1 << i;
    }
    public static bool OfFlag(this int value, int i) => (value & ToFlag(i)) > 0;
    public static int WithFlag(this int value, int i, bool f) => f ? (value | ToFlag(i)) : (value & ~ToFlag(i));
    public static int FlagCount(this int value) => int.PopCount(value);
    public static int HighestFlagIndex(this int value) => 31 - int.LeadingZeroCount(value);
}
0