最短路模版是黄，这题输入又很毒瘤，并且细节有很多，这已经绿了。构造图的方法也不好想，码量也大（$\text{2KB}$），我认为可以蓝。