Из пункта А в пункт С можно попасть по 4 маршрутам.
1) ABPMC = 37+22+26+17 = 102 km
2) ABPNC = 37+22+25+21 = 105 km
3) ADPMC = 42+19+26+17 = 104 km
4) ADPNC = 42+19+25+21 = 107 km
Ну и выбрать самый короткий путь очень легко - маршрут №1.
1000000 х 9 = 9000000
9000000 : 1000 = 9000