AtCoderのABC
前のABCの問題へ
ABC485-E Colorful Route
C#のソース
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("6 10");
WillReturn.Add("1 2 1");
WillReturn.Add("2 4 2");
WillReturn.Add("2 5 2");
WillReturn.Add("3 6 5");
WillReturn.Add("4 3 3");
WillReturn.Add("5 2 3");
WillReturn.Add("5 3 2");
WillReturn.Add("5 6 2");
WillReturn.Add("6 1 3");
WillReturn.Add("6 5 3");
//4
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 5");
WillReturn.Add("1 2 1");
WillReturn.Add("1 2 1");
WillReturn.Add("1 2 2");
WillReturn.Add("1 2 2");
WillReturn.Add("1 2 3");
//-1
}
else if (InputPattern == "Input3") {
WillReturn.Add("8 10");
WillReturn.Add("1 2 1");
WillReturn.Add("2 3 2");
WillReturn.Add("2 4 1");
WillReturn.Add("3 2 3");
WillReturn.Add("4 5 2");
WillReturn.Add("4 6 1");
WillReturn.Add("5 4 3");
WillReturn.Add("6 7 2");
WillReturn.Add("6 8 1");
WillReturn.Add("7 6 3");
//10
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
struct EdgeInfoDef
{
internal long ToNode;
internal long Color;
}
static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = GetSplitArr(InputList[0]);
long NodeCnt = wkArr[0];
Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
long FromNode = wkArr[0];
long ToNode = wkArr[1];
long Color = wkArr[2];
if (mEdgeInfoListDict.ContainsKey(FromNode) == false) {
mEdgeInfoListDict[FromNode] = new List<EdgeInfoDef>();
}
EdgeInfoDef WillAdd;
WillAdd.ToNode = ToNode;
WillAdd.Color = Color;
mEdgeInfoListDict[FromNode].Add(WillAdd);
}
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.CurrNode = 1;
WillEnqueue.SumCost = 0;
WillEnqueue.PrevColor = 0;
Que.Enqueue(WillEnqueue);
// 訪問数[ノード]なDict
var VisitedSet = new HashSet<long>();
// 訪問数[ノード]なDict
var VisitedCntDict = new Dictionary<long, long>();
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
if (Dequeued.CurrNode == NodeCnt) {
Console.WriteLine(Dequeued.SumCost);
return;
}
// 遷移
if (mEdgeInfoListDict.ContainsKey(Dequeued.CurrNode)) {
foreach (EdgeInfoDef EachEdge in mEdgeInfoListDict[Dequeued.CurrNode]) {
if (EachEdge.Color == Dequeued.PrevColor) continue;
WillEnqueue.CurrNode = EachEdge.ToNode;
WillEnqueue.SumCost = Dequeued.SumCost + 1;
WillEnqueue.PrevColor = EachEdge.Color;
// 最訪防止
long CurrHash = GetHash(WillEnqueue.CurrNode, WillEnqueue.PrevColor);
if (VisitedSet.Add(CurrHash) == false) {
continue;
}
// 枝切り
if (VisitedCntDict.ContainsKey(WillEnqueue.CurrNode)) {
if (VisitedCntDict[WillEnqueue.CurrNode] == 2) {
continue;
}
}
else {
VisitedCntDict[WillEnqueue.CurrNode] = 0;
}
VisitedCntDict[WillEnqueue.CurrNode]++;
Que.Enqueue(WillEnqueue);
}
}
}
Console.WriteLine(-1);
}
struct JyoutaiDef
{
internal long CurrNode;
internal long SumCost;
internal long PrevColor;
}
static long GetHash(long pNode, long pColor)
{
return pNode * 1000000 + pColor;
}
}
解説
頂点倍加で、{ノード、直前の色}をノードとし、
最訪防止のBFSすることを考えます。
BFSの計算量は、O(ノード数 + 枝数)であり、
{ノード、直前の色}で頂点倍加したら、
ノード数がNMあるので、ノード数の分だけでもTLEします。
そこで、ノードから色1,2,3,4,5の辺があるとして、枝切りを考えます。
1の色の辺から当該ノードに到達したら、色2,3,4,5の辺が使えます。
次の訪問で、1の色の辺以外から当該ノードに到達したら
色1の辺が使えます。
{ノード、直前の色}で最訪防止なBFSをしてることも考慮すると、
同じノードの3回目の訪問は、枝切りして良いと分かります。
これで、頂点倍加したグラフの、ノード数と枝数が激減するので
計算量を減らすことができ、TLEせずにACできます。