結果

問題 No.807 umg tours
コンテスト
ユーザー to_to_0121
提出日時 2019-03-22 23:39:24
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 5,407 bytes
コンパイル時間 2,182 ms
コンパイル使用メモリ 106,624 KB
実行使用メモリ 52,864 KB
最終ジャッジ日時 2024-09-19 07:05:48
合計ジャッジ時間 7,007 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 7 TLE * 1 -- * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Collections.Generic;
class Program
    {
        public class Node
        {
            public int id;
            public List<Edge> link = new List<Edge>();
            public int tourCost;
            public int ticketReduce;

            public Node(int i)
            {
                id = i;
                link = new List<Edge>();
                tourCost = -1;
                ticketReduce = 0;
            }
        }

        public class Edge
        {
            public int cost;
            public Node nodeFrom;
            public Node nodeTo;

            public Edge(Node f, Node t, int c)
            {
                cost = c; nodeFrom = f; nodeTo = t;
            }
        }

        static void connect (Node a, Node b, int c)
        {
            a.link.Add(new Edge(a, b, c));
            b.link.Add(new Edge(b, a, c));
            return;
        }

        static void addQueue(List<Node> queue, Node node)
        {
            int agent = -1;
            int danger = queue.Count;
            while (danger - agent > 1)
            {
                int middle = (agent + danger) / 2;
                //Console.Error.WriteLine("middle " + middle + " tourcost: " + node.tourCost);
                if (queue[middle].tourCost > node.tourCost) danger = middle;
                else agent = middle; 
            }
            queue.Insert(agent + 1, node);
        }
    	static void Main(string[] args)
    	{
            string[] input = Console.ReadLine().Split(' ');
            int n = int.Parse(input[0]), m = int.Parse(input[1]);
            List<Node> nodes = new List<Node>();
            for (int i=0; i<n; i++) nodes.Add(new Node(i));
            for (int i=0; i<m; i++)
            {
                string[] s = Console.ReadLine().Split(' ');
                connect(nodes[int.Parse(s[0]) - 1], nodes[int.Parse(s[1]) - 1], int.Parse(s[2]));
            }
            List<Node> queue = new List<Node>();
            nodes[0].tourCost = 0;
            queue.Add(nodes[0]);
            
            while(queue.Count > 0)
            {
                Node looking = queue[0];
                foreach(Edge edge in looking.link)
                {
                    
                    Node node = edge.nodeTo;
                    if (node.tourCost >= 0 && node.tourCost < looking.tourCost) continue;
                    if (edge.cost > looking.ticketReduce)
                    {
                        int newCost = looking.tourCost + looking.ticketReduce;
                        if (node.tourCost < 0)
                        {
                            node.tourCost = newCost;
                            node.ticketReduce = edge.cost;
                            addQueue(queue, node);
                        }
                        else if (newCost < node.tourCost)
                        {
                            node.tourCost = newCost;
                            node.ticketReduce = edge.cost;
                            if(queue.Contains(node)) queue.Remove(node);
                            addQueue(queue, node);
                        }
                    }
                    else{
                        int newCost = looking.tourCost + edge.cost;
                        if (node.tourCost < 0)
                        {
                            node.tourCost = newCost;
                            addQueue(queue, node);
                        }
                        else if (newCost < node.tourCost)
                        {
                            node.tourCost = newCost;
                            if(queue.Contains(node)) queue.Remove(node);
                            addQueue(queue, node);
                        }
                    }
                }
                queue.Remove(looking);
            }


            int[] cost1 = new int[n];
            for (int i=0; i<n; i++)
            {
                Node node = nodes[i];
                cost1[i] = node.tourCost;
                node.tourCost = -1;
            }
            nodes[0].tourCost = 0;
            queue = new List<Node>();
            queue.Add(nodes[0]);
            
            while(queue.Count > 0)
            {
                Node looking = queue[0];
                foreach(Edge edge in looking.link)
                {
                    Node node = edge.nodeTo;
                    if (node.tourCost >= 0 && node.tourCost < looking.tourCost) continue;
                    int newCost = looking.tourCost + edge.cost;
                    //Console.Error.WriteLine(newCost);
                    if (node.tourCost < 0)
                    {
                        node.tourCost = newCost;
                        addQueue(queue, node);
                    }
                    else if (newCost < node.tourCost)
                    {
                        node.tourCost = newCost;
                        if(queue.Contains(node)) queue.Remove(node);
                        addQueue(queue, node);
                    }
                }
                queue.Remove(looking);
            }

            int[] cost2 = new int[n];
            for (int i=0; i<n; i++)
            {
                cost2[i] = nodes[i].tourCost;
            }

            for(int i=0; i<n; i++) Console.WriteLine(cost1[i] + cost2[i]);
            
            
        }
    }
    //mcs Main.cs
    //mono Main.exe
0