結果

問題 No.807 umg tours
ユーザー keymoonkeymoon
提出日時 2019-03-22 23:05:23
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 5,446 bytes
コンパイル時間 2,083 ms
コンパイル使用メモリ 120,104 KB
実行使用メモリ 79,568 KB
最終ジャッジ日時 2024-09-19 06:30:05
合計ジャッジ時間 18,529 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
27,372 KB
testcase_01 AC 34 ms
25,480 KB
testcase_02 AC 38 ms
27,300 KB
testcase_03 AC 36 ms
25,512 KB
testcase_04 AC 34 ms
25,520 KB
testcase_05 AC 33 ms
25,352 KB
testcase_06 AC 36 ms
25,640 KB
testcase_07 AC 35 ms
25,260 KB
testcase_08 AC 34 ms
25,512 KB
testcase_09 RE -
testcase_10 RE -
testcase_11 AC 1,291 ms
67,980 KB
testcase_12 AC 810 ms
59,668 KB
testcase_13 AC 1,317 ms
72,220 KB
testcase_14 AC 479 ms
46,792 KB
testcase_15 AC 359 ms
43,788 KB
testcase_16 AC 1,418 ms
70,516 KB
testcase_17 AC 1,669 ms
79,568 KB
testcase_18 AC 1,658 ms
77,784 KB
testcase_19 AC 1,654 ms
78,116 KB
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 797 ms
67,092 KB
testcase_25 AC 1,741 ms
79,436 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static void Main()
    {
        //頂点それぞれについてツアー
        //1→i→1
        //単一始点最短路を打って
        //1減る ということを
        var nm = Console.ReadLine().Split().Select(int.Parse).ToList();
        List<Tuple<int, int>>[] neighbour = Enumerable.Repeat(0, nm[0]).Select(_ => new List<Tuple<int, int>>()).ToArray();

        for (int i = 0; i < nm[1]; i++)
        {
            var abc = Console.ReadLine().Split().Select(int.Parse).ToList();
            neighbour[abc[0] - 1].Add(new Tuple<int, int>(abc[1] - 1, abc[2]));
            neighbour[abc[1] - 1].Add(new Tuple<int, int>(abc[0] - 1, abc[2]));
        }

        //0-(n-1) : 通常の点
        //n-(2*n-1) : 既にvipチケ使った点
        int[] distances = Enumerable.Repeat(-1, nm[0] * 2).ToArray();
        //PriorityQueue<Tuple<int, int>> pqueue = new PriorityQueue<Tuple<int, int>>(nm[1]);
        Heap pqueue = new Heap(nm[1] * 3);
        pqueue.Push(new Tuple<int, int>(0, 0));
        while (pqueue.Count > 0)
        {
            var item = pqueue.Pop();
            Debug.WriteLine($"{item.Item2} {item.Item1}");
            if (distances[item.Item2] >= 0) continue;
            distances[item.Item2] = item.Item1;

            if (item.Item2 >= nm[0])
            {
                foreach (var edge in neighbour[item.Item2 - nm[0]])
                {
                    pqueue.Push(new Tuple<int, int>(item.Item1 + edge.Item2, edge.Item1 + nm[0]));
                }
            }
            else
            {
                foreach (var edge in neighbour[item.Item2])
                {
                    pqueue.Push(new Tuple<int, int>(item.Item1 + edge.Item2, edge.Item1));
                    pqueue.Push(new Tuple<int, int>(item.Item1, edge.Item1 + nm[0]));
                }
            }
        }
        Console.WriteLine(string.Join("\n", distances.Zip(distances.Skip(nm[0]), (x, y) => x + Min(x, y))));
    }
}

//  Microsoft Windows Client Platform
//  Copyright (C) Microsoft Corporation. All rights reserved.
internal class PriorityQueue<T> where T : IComparable
{
    private T[] _heap;
    private const int DefaultCapacity = 6;

    public PriorityQueue(int capacity)
    {
        Count = 0;
        _heap = new T[capacity > 0 ? capacity : DefaultCapacity];
    }
    
    public int Count { get; set; }

    public T Top
    {
        get
        {
            Debug.Assert(Count > 0);
            return _heap[0];
        }
    }

    public void Push(T value)
    {
        if (Count == _heap.Length)
        {
            T[] temp = new T[Count * 2];
            for (int i = 0; i < Count; ++i)
            {
                temp[i] = _heap[i];
            }
            _heap = temp;
        }
        
        int index = Count;
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (value.CompareTo(_heap[parentIndex]) >= 0) break;
            _heap[index] = _heap[parentIndex];
            index = parentIndex;
        }

        _heap[index] = value;
        Count++;
    }
    
    public T Pop()
    {
        T top = Top;
        Debug.Assert(Count != 0);
        if (Count > 1)
        {
            int parent = 0;
            int leftChild = (parent * 2) + 1;

            while (leftChild < Count)
            {
                int rightChild = leftChild + 1;
                int bestChild = (rightChild < Count && _heap[rightChild].CompareTo(_heap[leftChild]) < 0) ? rightChild : leftChild;
                
                _heap[parent] = _heap[bestChild];

                parent = bestChild;
                leftChild = (parent * 2) + 1;
            }

            _heap[parent] = _heap[Count - 1];
        }
        Count--;
        return top;
    }
}

class Heap
{
    public int Count;
    Tuple<int, int>[] obj;
    public Heap(int maxsize)
    {
        Count = 0;
        obj = new Tuple<int, int>[maxsize];
    }
    public void Push(Tuple<int, int> a)
    {
        int i = Count;
        Count++;
        while (i > 0)
        {
            int p = (i - 1) / 2;
            if (obj[p].Item1 <= a.Item1)
            {
                obj[i] = a;
                break;
            }
            obj[i] = obj[p];
            i = p;
        }
        if (i == 0)
        {
            obj[0] = a;
        }
    }
    public Tuple<int, int> Pop()
    {
        Tuple<int, int> t = obj[0];
        int i = 0;
        Count--;
        while (2 * i + 1 < Count)
        {
            int p = 2 * i + 1;
            if (p + 1 < Count && obj[p + 1].Item1 < obj[p].Item1)
            {
                p++;
            }
            if (obj[p].Item1 < obj[Count].Item1)
            {
                obj[i] = obj[p];
                i = p;
            }
            else
            {
                obj[i] = obj[Count];
                break;
            }
        }
        if (2 * i + 1 >= Count)
        {
            obj[i] = obj[Count];
        }
        return t;
    }
}
0