D - Cow and Fields

題意 給出n個點，m條邊，還有k個特殊點；

求從1到n的最短路，但又不是單純求最短；

我們需要在這k個特殊點中選擇兩個點，将這兩個點相連，再去求路徑最長的最短路

那麼 ，我們可以先跑兩邊spfa求出從頂點1開始的最短路和從n開始的最短路，分别為disa disb；

然後，我們再将特殊點根據disa[x]-disb[x]<disa[y]-disb[y]，來排序；

為啥這樣排呢，因為  disa[x]+1+disn[y]<disa[y]+1+disn[x],  移項之後便是上面的式子；

為什麼是這樣的式子呢，首先我們就要确定排序的宗旨，就是讓路徑是從1到x，從x到y，再從y到n;

而不是從1到y，從y到x，再從x到n 這樣子就繞了個圈；我們也不好判斷；

是以我們将特殊點處理為不用“繞圈子"的樣子，這樣我們就可以O(n)的複雜度來周遊；

是以，要讓答案最大，我們就在每次更新完ans之後，再更新一下特殊點的左端點（根據距點1的距離更遠更優來選擇）

這樣子代碼基本就完成；

但是有一個細節；

就是可能特殊點對最短路沒有貢獻，意思就是，即使連接配接了這兩個特殊點，得出的答案依舊為inf

是以我們最後得ans=min(ans,disa[n]);

代碼如下：