Supercomputing Contest 2012/本選問題

Supercomputing Contest 2012

都市伝説：不可思議トライアングル †

大都市の複雑な電車網では，１日中電車に乗っている２人が，まったく出会わない，ということも十分起こりうる．たとえ，それが３人であってもだ.

非出会い系最長乗車パターン †

ある都市の電車網（例：下図）における１日の電車の運行スケジュールが与えられる．そこから，３人が，始発から終電まで１度も同じ駅で出会わないような電車の乗り方のうち，３人の合計走行距離が最も長くなるものを求めよ．

条件 †

• 電車は分刻みで運行
• 1日は4:00〜24:00の20時間 (1200分間)
• 駅の停車時間は0分。また、0分で乗り換えも可能。
• 急行、快速などもあり、超複々線。
• ある時刻に同じ駅にいるだけでなく、同じ駅に止まる電車にのっていても出会ったとみなす。