結果
| 問題 |
No.17 2つの地点に泊まりたい
|
| コンテスト | |
| ユーザー |
 明智重蔵
|
| 提出日時 | 2016-02-07 16:26:36 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,427 bytes |
| コンパイル時間 | 2,482 ms |
| コンパイル使用メモリ | 110,848 KB |
| 実行使用メモリ | 24,320 KB |
| 最終ジャッジ日時 | 2024-09-21 21:33:00 |
| 合計ジャッジ時間 | 17,813 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 27 |
コンパイルメッセージ
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.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4");
WillReturn.Add("0");
WillReturn.Add("2");
WillReturn.Add("100");
WillReturn.Add("0");
WillReturn.Add("5");
WillReturn.Add("0 1 1");
WillReturn.Add("0 2 1");
WillReturn.Add("1 2 1");
WillReturn.Add("1 3 1");
WillReturn.Add("2 3 2");
//105
//地点は全部で4個。
//地点1と地点2にはかならず滞在しなければならない。
//0→2→1→3 の順番で移動し、
//地点1と地点2に滞在したとき最小コストになる。
}
else if (InputPattern == "Input2") {
WillReturn.Add("4");
WillReturn.Add("0");
WillReturn.Add("3");
WillReturn.Add("3");
WillReturn.Add("0");
WillReturn.Add("3");
WillReturn.Add("0 1 1");
WillReturn.Add("1 3 2");
WillReturn.Add("2 3 4");
//17
//地点1と地点2にはかならず滞在しなければならない。
//よって、0→1→3→2→3 のような移動が必要。
//同じ地点を2度通っても良い。
}
else if (InputPattern == "Input3") {
WillReturn.Add("16");
WillReturn.Add("0");
WillReturn.Add("15");
WillReturn.Add("6");
WillReturn.Add("23");
WillReturn.Add("8");
WillReturn.Add("193");
WillReturn.Add("14");
WillReturn.Add("13");
WillReturn.Add("53");
WillReturn.Add("16");
WillReturn.Add("85");
WillReturn.Add("12");
WillReturn.Add("15");
WillReturn.Add("5");
WillReturn.Add("14");
WillReturn.Add("0");
WillReturn.Add("15");
WillReturn.Add("0 1 17");
WillReturn.Add("14 15 18");
WillReturn.Add("7 8 87");
WillReturn.Add("4 5 137");
WillReturn.Add("8 9 17");
WillReturn.Add("11 12 33");
WillReturn.Add("5 6 177");
WillReturn.Add("9 10 47");
WillReturn.Add("10 11 27");
WillReturn.Add("1 2 77");
WillReturn.Add("6 7 114");
WillReturn.Add("12 13 15");
WillReturn.Add("2 3 127");
WillReturn.Add("13 14 11");
WillReturn.Add("3 4 85");
//1000
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct JyoutaiDef
{
internal int CurrPos;
internal int MoveCost;
internal List<int> SyukuhakuIndList;
internal string Path;
}
struct MemoInfoDef
{
internal int MoveCost;
internal int SyukuhakuCost;
}
static void Main()
{
List<string> InputList = GetInputList();
int N = int.Parse(InputList[0]);
var SList = new List<int>();
foreach (string EachStr in InputList.Skip(1).Take(N)) {
SList.Add(int.Parse(EachStr));
}
int[] SArr = SList.ToArray();
//隣接行列で枝を表現
int[,] RinsetuGyouretu = new int[N, N];
foreach (string EachStr in InputList.Skip(1 + N + 1)) {
int[] wkArr = EachStr.Split(' ').Select(X => int.Parse(X)).ToArray();
RinsetuGyouretu[wkArr[0], wkArr[1]] = wkArr[2];
RinsetuGyouretu[wkArr[1], wkArr[0]] = wkArr[2];
}
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrPos = 0;
WillPush.MoveCost = 0;
WillPush.SyukuhakuIndList = new List<int>();
WillPush.Path = "0,";
stk.Push(WillPush);
//コスト情報のList[移動先ノード,宿の数]なメモの配列
var MemoListArr = new List<MemoInfoDef>[N, 2 + 1];
for (int I = 0; I <= MemoListArr.GetUpperBound(0); I++)
for (int J = 0; J <= MemoListArr.GetUpperBound(1); J++)
MemoListArr[I, J] = new List<MemoInfoDef>();
int Answer = int.MaxValue;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.CurrPos == N - 1
&& Popped.SyukuhakuIndList.Count == 2) {
int SumCost = Popped.MoveCost + Popped.SyukuhakuIndList.Sum(X => SArr[X]);
if (Answer > SumCost) {
Answer = SumCost;
Console.WriteLine("解候補を発見");
Console.WriteLine("SumCost={0}", SumCost);
Console.WriteLine("宿1は、ノード{0},宿泊コスト={1}",
Popped.SyukuhakuIndList[0], SArr[Popped.SyukuhakuIndList[0]]);
Console.WriteLine("宿2は、ノード{0},宿泊コスト={1}",
Popped.SyukuhakuIndList[1], SArr[Popped.SyukuhakuIndList[1]]);
Console.WriteLine("Path={0}", Popped.Path);
}
}
for (int LoopJ = 0; LoopJ <= N - 1; LoopJ++) {
if (RinsetuGyouretu[Popped.CurrPos, LoopJ] == 0) continue;
WillPush.SyukuhakuIndList = Popped.SyukuhakuIndList;
//宿泊コストの更新処理
if (0 < LoopJ && LoopJ < N - 1
&& Popped.SyukuhakuIndList.Contains(LoopJ) == false) {
int NewSyukuhakuCost = SArr[LoopJ];
if (Popped.SyukuhakuIndList.Count <= 1
|| NewSyukuhakuCost < Popped.SyukuhakuIndList.Max(X => SArr[X])) {
WillPush.SyukuhakuIndList = new List<int>(Popped.SyukuhakuIndList);
WillPush.SyukuhakuIndList.Add(LoopJ);
WillPush.SyukuhakuIndList =
WillPush.SyukuhakuIndList.OrderBy(X => SArr[X]).Take(2).ToList();
}
}
WillPush.CurrPos = LoopJ;
WillPush.MoveCost = Popped.MoveCost + RinsetuGyouretu[Popped.CurrPos, LoopJ];
WillPush.Path = Popped.Path + LoopJ.ToString() + ",";
//メモ化探索
int MoveCost = WillPush.MoveCost;
int SyukuhakuCost = WillPush.SyukuhakuIndList.Sum(X => SArr[X]);
int SyukuhakuCnt = WillPush.SyukuhakuIndList.Count;
if (MemoListArr[WillPush.CurrPos, SyukuhakuCnt].Exists(X =>
X.MoveCost <= MoveCost && X.SyukuhakuCost <= SyukuhakuCost)) {
continue;
}
MemoInfoDef WillAdd;
WillAdd.MoveCost = MoveCost;
WillAdd.SyukuhakuCost = SyukuhakuCost;
MemoListArr[WillPush.CurrPos, SyukuhakuCnt].Add(WillAdd);
//下限値枝切り
if (Answer <= MoveCost) continue;
stk.Push(WillPush);
}
}
Console.WriteLine(Answer);
}
}