出入口が2箇所のものは簡単で、 その2箇所を発着として、その他の駅は線の交点になる駅だけピックアップして 最長経路を求めればいいです。 出入口が3箇所のものもさほど難しくありません。 出入口の駅A-駅B, 駅B-駅C, 駅A-駅Cを発着とする最長経路3種類を求めればいいです。 問題は、出入口が4箇所以上あるものです。 JRとメトロです。 3箇所と同じように、駅A-駅B, 駅A-駅C, 駅A-駅D, 駅B-駅C, 駅B-駅D, 駅C-駅Dを 発着とする最長経路を求めれば良いでしょうか?違います。 駅A-駅B-(外部)-駅C-駅Dのような経路も考えられます。 この時、A-BとC-Dの経路は重なってはいけません。 ではそれを解くために、端点となる駅を4つ投入すればいいじゃないか。 と最初はそう思いました。 しかし、整数計画法に解かせる都合上、それも上手くいきません。 整数計画法では「どの点とどの