結果

問題 No.3263 違法な散歩道
ユーザー tobisatis
提出日時 2025-09-06 13:38:50
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 706 ms / 2,000 ms
コード長 3,726 bytes
コンパイル時間 8,990 ms
コンパイル使用メモリ 170,392 KB
実行使用メモリ 253,400 KB
最終ジャッジ日時 2025-09-06 13:40:03
合計ジャッジ時間 22,168 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (113 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

using System.Numerics;

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

var n = I<int>();
var m = I<int>();
var oez = Range(m, () => (I<int>() - 1, I<int>() - 1));
var k = I<int>();
var iwiz = new bool[n];
for (var i = 0; i < k; i++) iwiz[I<int>() - 1] = true;
var edges = new List<(int, int)>();
for (var i = 0; i < m; i++)
{
    var (u, v) = oez[i];
    for (var _i = 0; _i < 2; _i++)
    {
        if (iwiz[v])
        {
            for (var t = 0; t <= 3; t++)
            {
                edges.Add((u + t * n, v + (t + 1) * n));
            }
        }
        else
        {
            for (var t = 0; t <= 4; t++)
            {
                edges.Add((u + t * n, v));
            }
        }
        (u, v) = (v, u);
    }
}
var dz = new int[edges.Count];
dz.AsSpan().Fill(1);
var sg = new StaticGraph(edges, n * 5, true);
var max = int.MaxValue / 2;
var spz = Distances(new(){ StaticGraph = sg }, 0, dz, max);
var ans = max;
for (var i = 0; i <= 4; i++) ans = Math.Min(ans, spz[n - 1 + i * n].d);
if (ans == max) ans = -1;
Console.WriteLine(ans);

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

static Span<(T d, int prevE, int prevV)> Distances<T>(
    Graph graph,
    int start,
    IReadOnlyList<T> distances,
    T infinity
)
    where T : IComparable<T>, INumber<T>
{
    var g = graph.StaticGraph;
    var res = new (T, int, int)[g.N].AsSpan();
    for (var i = 0; i < res.Length; i++) res[i] = (infinity, -1, -1);
    var determined = new bool[g.N].AsSpan();
    var q = new PriorityQueue<int, T>();
    q.Enqueue(start, res[start].Item1 = T.AdditiveIdentity);
    while (q.Count > 0)
    {
        var v = q.Dequeue();
        if (determined[v]) continue;
        determined[v] = true;
        var adjacencies = g.Adjacencies(v);
        foreach (var (next, ei) in adjacencies)
        {
            var d = res[v].Item1 + distances[ei];
            if (res[next].Item1.CompareTo(d) <= 0) continue;
            res[next] = (d, v, ei);
            q.Enqueue(next, d);
        }
    }
    return res;
}

class StaticGraph
{
    public int N { get; }
    public bool Directed { get; }
    public ReadOnlySpan<(int next, int edgeIndex)> Adjacencies(int of) => _adjacencyList.Span[of].Span;
    public ReadOnlySpan<(int Ab, int Ad)> Edges => _edges.Span;

    readonly ReadOnlyMemory<ReadOnlyMemory<(int, int)>> _adjacencyList;
    readonly ReadOnlyMemory<(int Ab, int Ad)> _edges;

    public StaticGraph(IReadOnlyList<(int, int)> edges, int verticals, bool directed)
    {
        (N, Directed) = (verticals, directed);
        var al = new List<(int, int)>[verticals];
        for (var i = 0; i < verticals; i++) al[i] = new();
        _edges = edges.ToArray();
        for (var i = 0; i < edges.Count; i++)
        {
            var (ab, ad) = edges[i];
            al[ab].Add((ad, i));
            if (!Directed) al[ad].Add((ab, i));
        }
        var ala = new ReadOnlyMemory<(int, int)>[verticals];
        var dataMemory = new (int, int)[directed ? edges.Count : edges.Count * 2].AsMemory();
        var dataSpan = dataMemory.Span;
        var k = 0;
        for (var i = 0; i < verticals; i++)
        {
            var length = al[i].Count;
            for (var j = 0; j < length; j++) dataSpan[k + j] = al[i][j];
            ala[i] = dataMemory.Slice(k, length);
            k += length;
        }
        _adjacencyList = ala;
    }
}

class Graph { public required StaticGraph StaticGraph { get; init; } }
0