結果
| 問題 |
No.1283 Extra Fee
|
| コンテスト | |
| ユーザー |
👑  terry_u16
|
| 提出日時 | 2020-11-06 22:11:24 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 1,278 ms / 2,000 ms |
| コード長 | 15,992 bytes |
| コンパイル時間 | 1,152 ms |
| コンパイル使用メモリ | 123,720 KB |
| 実行使用メモリ | 126,220 KB |
| 最終ジャッジ日時 | 2024-11-16 06:42:51 |
| 合計ジャッジ時間 | 19,262 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
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;
using System.IO;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using YukicoderContest273.Extensions;
using YukicoderContest273.Questions;
using YukicoderContest273.Graphs;
using YukicoderContest273.Graphs.Algorithms;
namespace YukicoderContest273.Questions
{
public class QuestionE : AtCoderQuestionBase
{
public override IEnumerable<object> Solve(TextReader inputStream)
{
var (n, feeCount) = inputStream.ReadValue<int, int>();
var nodeCount = n * n;
var feeMap = new int[n, n];
for (int i = 0; i < feeCount; i++)
{
var (r, c, cost) = inputStream.ReadValue<int, int, int>();
r--;
c--;
feeMap[r, c] = cost;
}
var graph = new WeightedGraph(nodeCount * 2);
var diffs = new (int dr, int dc)[] { (-1, 0), (1, 0), (0, -1), (0, 1) };
for (int row = 0; row < n; row++)
{
for (int column = 0; column < n; column++)
{
foreach (var diff in diffs)
{
var (dr, dc) = diff;
var nextRow = row + dr;
var nextColumn = column + dc;
if (unchecked((uint)nextRow < (uint)n && (uint)nextColumn < (uint)n))
{
graph[GetIndex(row, column, n)].Add(new WeightedEdge(GetIndex(nextRow, nextColumn, n), 1 + feeMap[nextRow, nextColumn]));
graph[GetIndex(row, column, n)].Add(new WeightedEdge(GetIndex(nextRow, nextColumn, n) + nodeCount, 1));
graph[GetIndex(row, column, n) + nodeCount].Add(new WeightedEdge(GetIndex(nextRow, nextColumn, n) + nodeCount, 1 + feeMap[nextRow, nextColumn]));
}
}
}
}
var dijkstra = new Dijkstra(graph);
var costs = dijkstra.GetDistancesFrom(0);
yield return costs[costs.Length - 1];
}
int GetIndex(int row, int column, int n) => row * n + column;
}
}
namespace YukicoderContest273
{
class Program
{
static void Main(string[] args)
{
IAtCoderQuestion question = new QuestionE();
var answers = question.Solve(Console.In);
var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(writer);
foreach (var answer in answers)
{
Console.WriteLine(answer);
}
Console.Out.Flush();
}
}
}
#region Base Class
namespace YukicoderContest273.Questions
{
public interface IAtCoderQuestion
{
IEnumerable<object> Solve(string input);
IEnumerable<object> Solve(TextReader inputStream);
}
public abstract class AtCoderQuestionBase : IAtCoderQuestion
{
public IEnumerable<object> Solve(string input)
{
var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
var reader = new StreamReader(stream, Encoding.Unicode);
return Solve(reader);
}
public abstract IEnumerable<object> Solve(TextReader inputStream);
}
}
#endregion
#region Extensions
namespace YukicoderContest273.Extensions
{
public static class StringExtensions
{
public static string Join<T>(this IEnumerable<T> source) => string.Concat(source);
public static string Join<T>(this IEnumerable<T> source, char separator) => string.Join(separator, source);
public static string Join<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);
}
public static class TextReaderExtensions
{
public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
public static string ReadString(this TextReader reader) => reader.ReadLine();
public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
// Supports primitive type only.
public static T1 ReadValue<T1>(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1));
public static (T1, T2) ReadValue<T1, T2>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
return (v1, v2);
}
public static (T1, T2, T3) ReadValue<T1, T2, T3>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
return (v1, v2, v3);
}
public static (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
return (v1, v2, v3, v4);
}
public static (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
return (v1, v2, v3, v4, v5);
}
public static (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
return (v1, v2, v3, v4, v5, v6);
}
public static (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));
return (v1, v2, v3, v4, v5, v6, v7);
}
public static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue<T1, T2, T3, T4, T5, T6, T7, T8>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));
var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8));
return (v1, v2, v3, v4, v5, v6, v7, v8);
}
}
}
#endregion
namespace YukicoderContest273.Graphs
{
public interface IEdge
{
int To { get; }
}
public interface IWeightedEdge : IEdge
{
long Weight { get; }
}
public interface IGraph<TEdge> where TEdge : IEdge
{
List<TEdge> this[int node] { get; }
int NodeCount { get; }
}
public interface IWeightedGraph<TEdge> : IGraph<TEdge> where TEdge : IWeightedEdge { }
public readonly struct BasicEdge : IEdge
{
public int To { get; }
public BasicEdge(int to)
{
To = to;
}
public override string ToString() => To.ToString();
public static implicit operator BasicEdge(int edge) => new BasicEdge(edge);
public static implicit operator int(BasicEdge edge) => edge.To;
}
[StructLayout(LayoutKind.Auto)]
public readonly struct WeightedEdge : IWeightedEdge
{
public int To { get; }
public long Weight { get; }
public WeightedEdge(int to) : this(to, 1) { }
public WeightedEdge(int to, long weight)
{
To = to;
Weight = weight;
}
public override string ToString() => $"[{Weight}]-->{To}";
public void Deconstruct(out int to, out long weight) => (to, weight) = (To, Weight);
}
public class WeightedGraph : IGraph<WeightedEdge>
{
private readonly List<List<WeightedEdge>> _edges;
public List<WeightedEdge> this[int node] => _edges[node];
public int NodeCount => _edges.Count;
public WeightedGraph(int nodeCount)
{
_edges = new List<List<WeightedEdge>>(nodeCount);
for (int i = 0; i < nodeCount; i++)
{
_edges.Add(new List<WeightedEdge>());
}
}
public void AddEdge(int from, int to, long weight) => _edges[from].Add(new WeightedEdge(to, weight));
public void AddNode() => _edges.Add(new List<WeightedEdge>());
}
public class PriorityQueue<T> : IEnumerable<T> where T : IComparable<T>
{
private List<T> _heap = new List<T>();
private readonly int _reverseFactor;
public int Count => _heap.Count;
public bool IsDescending => _reverseFactor == 1;
public PriorityQueue(bool descending) : this(descending, null) { }
public PriorityQueue(bool descending, IEnumerable<T> collection)
{
_reverseFactor = descending ? 1 : -1;
_heap = new List<T>();
if (collection != null)
{
foreach (var item in collection)
{
Enqueue(item);
}
}
}
public void Enqueue(T item)
{
_heap.Add(item);
UpHeap();
}
public T Dequeue()
{
var item = _heap[0];
DownHeap();
return item;
}
public T Peek() => _heap[0];
private void UpHeap()
{
var child = Count - 1;
while (child > 0)
{
int parent = (child - 1) / 2;
if (Compare(_heap[child], _heap[parent]) > 0)
{
SwapAt(child, parent);
child = parent;
}
else
{
break;
}
}
}
private void DownHeap()
{
_heap[0] = _heap[Count - 1];
_heap.RemoveAt(Count - 1);
var parent = 0;
while (true)
{
var leftChild = 2 * parent + 1;
if (leftChild > Count - 1)
{
break;
}
var target = (leftChild < Count - 1) && (Compare(_heap[leftChild], _heap[leftChild + 1]) < 0) ? leftChild + 1 : leftChild;
if (Compare(_heap[parent], _heap[target]) < 0)
{
SwapAt(parent, target);
}
else
{
break;
}
parent = target;
}
}
private int Compare(T a, T b) => _reverseFactor * a.CompareTo(b);
private void SwapAt(int n, int m) => (_heap[n], _heap[m]) = (_heap[m], _heap[n]);
public IEnumerator<T> GetEnumerator()
{
var copy = new List<T>(_heap);
try
{
while (Count > 0)
{
yield return Dequeue();
}
}
finally
{
_heap = copy;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
}
namespace Algorithms
{
public class Dijkstra
{
private readonly WeightedGraph _graph;
public Dijkstra(WeightedGraph graph)
{
_graph = graph;
}
public long[] GetDistancesFrom(int startNode)
{
const long Inf = 1L << 60;
var distances = Enumerable.Repeat(Inf, _graph.NodeCount).ToArray();
distances[startNode] = 0;
var todo = new PriorityQueue<State>(false);
todo.Enqueue(new State(startNode, 0));
while (todo.Count > 0)
{
var current = todo.Dequeue();
if (current.Distance > distances[current.Node])
{
continue;
}
for (int i = 0; i < _graph[current.Node].Count; i++)
{
var edge = _graph[current.Node][i];
var nextDistance = current.Distance + edge.Weight;
if (distances[edge.To] > nextDistance)
{
distances[edge.To] = nextDistance;
todo.Enqueue(new State(edge.To, nextDistance));
}
}
}
return distances;
}
private readonly struct State : IComparable<State>
{
public int Node { get; }
public long Distance { get; }
public State(int node, long distance)
{
Node = node;
Distance = distance;
}
public int CompareTo(State other) => Distance.CompareTo(other.Distance);
public void Deconstruct(out int node, out long distance) => (node, distance) = (Node, Distance);
}
}
}
}