Dijkstra, less查

今天做一題dijkstra時，第一次submit TLE，然後加了一句優化再submit就變15ms了
其實那句平時都有打，只是剛好這次懶沒打... 想不到影響這麼大

假設用pair作為heap的index，first=path length，second=node number ; dis[x] 為 dis[start] 到 x 暫時的shortest path

while (!q.empty())
     t=q.top();
     q.pop();
     if (t.first>dis[goal]) break;
     for all v visit by t.second
          if (e[t.second][v]+t.first<dis[v])
                dis[v]=e[t.second][v]+t.first;                
                push v into q;

加了紅色那句後，原理是如果heap頂的shortest path distance己經大於己找到去終點的shortest path distance，由於沒有negative edge，之後找到的path都不會比現有的更短，因此可以查少幾條path

所以 Dijkstra 又名 less查 是有道理的