結果
| 問題 | No.807 umg tours |
| ユーザー |
 to_to_0121
|
| 提出日時 | 2019-03-22 23:50:15 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,421 bytes |
| コンパイル時間 | 2,090 ms |
| コンパイル使用メモリ | 113,440 KB |
| 実行使用メモリ | 81,804 KB |
| 最終ジャッジ日時 | 2024-09-19 07:08:34 |
| 合計ジャッジ時間 | 7,571 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | AC | 28 ms
18,176 KB |
| testcase_07 | WA | - |
| testcase_08 | AC | 26 ms
17,792 KB |
| testcase_09 | AC | 25 ms
17,792 KB |
| testcase_10 | AC | 26 ms
18,176 KB |
| testcase_11 | TLE | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
class Program
{
public class Node
{
public int id;
public List<Edge> link = new List<Edge>();
public long 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)
{
long newCost = (long)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{
long 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);
}
long[] cost1 = new long[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;
long 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);
}
long[] cost2 = new long[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