結果

問題 No.807 umg tours
コンテスト
ユーザー keymoon
提出日時 2019-03-22 23:12:05
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,274 bytes
コンパイル時間 1,017 ms
コンパイル使用メモリ 111,360 KB
実行使用メモリ 300,888 KB
最終ジャッジ日時 2024-09-19 06:35:19
合計ジャッジ時間 17,892 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 18 TLE * 1 -- * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
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], (x, y) => x.Item1 < y.Item1);
        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;
    Func<T, T, bool> Larger;

    public PriorityQueue(int capacity, Func<T, T, bool> larger)
    {
        Count = 0;
        _heap = new T[capacity > 0 ? capacity : DefaultCapacity];
        Larger = larger;
    }
    
    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 (!Larger(value, _heap[parentIndex])) 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 && Larger(_heap[rightChild], _heap[leftChild])) ? rightChild : leftChild;
                
                _heap[parent] = _heap[bestChild];

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

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