Dijkstra with STL priority_queue 優先隊列

Dijkstra算法是一個經典的求單源最短路的算法，經過堆優化的Dijkstra算法有着良好的性能，雖然Heap的代碼複雜度並不算很高，但是至少也會爲程序的調試帶來一些麻煩。現在C++ STL開放了，所以可以用STL中的PQ容器（優先級隊列）來實現堆。

例題：

【題目描述】

在某個遙遠的國家裏，有n個城市。編號爲1，2，3，……，n。

這個國家的政府修建了m條雙向的公路。每條公路連接着兩個城市。沿着某條公路，開車從一個城市到另一個城市，需要花費一定的汽油。

開車每經過一個城市，都會被收取一定的費用（包括起點和終點城市）。所有的收費站都在城市中，在城市間的公路上沒有任何的收費站。

小紅現在要開車從城市u到城市v(1<=u，v<=n)。她的車最多可以裝下s升的汽油。在出發的時候，車的油箱是滿的，並且她在路上不想加油。

在路上，每經過一個城市，她要交一定的費用。如果她某次交的費用比較多，她的心情就會變得很糟。所以她想知道，在她能到達目的地的前提下，她交的費用中最多的一次最少是多少。這個問題對於她來說太難了，於是她找到了聰明的你，你能幫幫她嗎？

【輸入格式】

第一行5個正整數，n，m，u，v，s。分別表示有n個城市，m條公路，從城市u到城市v，車的油箱的容量爲s升。

接下來有n行，每行1個正整數，fi。表示經過城市i，需要交費fi元。

再接下來有m行，每行3個正整數，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之間有一條公路，如果從城市ai到城市bi，或者從城市bi到城市ai，需要用ci升汽油。

【輸出格式】

僅一個整數，表示小紅交費最多的一次的最小值。

如果她無法到達城市v，輸出-1。

【輸入樣例1】

4 4 2 3 8

8

5

6

10

2 1 2

2 4 1

1 3 4

3 4 3

【輸出樣例1】

8

【輸入樣例2】

4 4 2 3 3

8

5

6

10

2 1 2

2 4 1

1 3 4

3 4 3

【輸出樣例2】

-1

【數據規模】

對於60%的數據，滿足n<=200，m<=10000，s<=200

對於100%的數據，滿足n<=10000，m<=50000，s<=1000000000

對於100%的數據，滿足ci<=1000000000，fi<=1000000000，可能有兩條邊連接着相同的城市。

[分析]

這道題是道判定類題目，算法是二分答案+單源最短路。

由於數據很大，二分N+SPFA會超時1組，所以考慮Dijkstra+Heap。

[我的代碼]

C++语言: Codee#25838

001 /*
002 *Problem: NOIP模擬題 收費站
003 *Author: YeefanZhu
004 *Website: www.yeefanblog.tk
005 *GTalk: zyfworks@gmail.com
006 */
007 #include <cstdio>
008 #include <vector>
009 #include <cstdlib>
010 #include <algorithm>
011 #include <queue>
012 using namespace std;
013 const int MAXN=10001;
014 const int INF=1100000000;
015 int Cost[MAXN],BS[MAXN];
016 int N,M,S,B,E;
017 vector<int> Map[MAXN];
018 vector<int>Val[MAXN];
019
020 inline void init()
021 {
022     scanf("%d %d %d %d %d\n",&N,&M,&B,&E,&S);
023     for(int i=1;i<=N;i++)
024     {
025         scanf("%d\n",&Cost[i]);
026         BS[i]=Cost[i];
027     }
028     sort(BS+1,BS+N+1);
029     int a,b,v;
030     for(int i=1;i<=M;i++)
031     {
032         scanf("%d %d %d\n",&a,&b,&v);
033         Map[a].push_back(b);
034         Map[b].push_back(a);
035         Val[a].push_back(v);
036         Val[b].push_back(v);
037     }
038 }
039
040 priority_queue<pair<int,int> > PQ;
041 int Used[MAXN];
042 int Dist[MAXN];
043
044 inline bool SP(int x)
045
046 {
047     if(Cost[B]>x) return false;
048     for(int i=1;i<=N;i++) {Used[i]=0,Dist[i]=INF;}
049     Dist[B]=0;
050     PQ.push(make_pair(0,B));
051     int u,v,cost;
052     while(!PQ.empty())
053     {
054         u=PQ.top().second;
055         PQ.pop();
056         if(!Used[u])
057         {
058             Used[u]=1;
059             for(unsigned int i=0;i<Map[u].size();i++)
060             {
061                 v=Map[u][i];
062                 cost=Val[u][i];
063                 if(Cost[v]>x) continue;
064                 if(!Used[v]&&Dist[v]-Dist[u]>cost)
065                 {
066                     Dist[v]=Dist[u]+cost;
067                     PQ.push(make_pair(-Dist[v],v));
068                 }
069             }
070         }
071     }
072     if(Dist[E]>S) return false;
073     return true;
074 }
075
076 inline void solve()
077 {
078     int L=1,R=N;
079     int Mid;
080     if(!SP(BS[N])) {printf("-1\n");return;}
081     int Ans;
082     bool flag;
083     while(L<=R)
084     {
085         Mid=(L+R)>>1;
086         flag=SP(BS[Mid]);
087         if(flag)
088         {
089             Ans=BS[Mid];
090             R=Mid-1;
091         }
092         else L=Mid+1;
093     }
094     printf("%d\n",Ans);
095 }
096
097 int main()
098 {
099     freopen("cost.in","r",stdin);
100     freopen("cost.out","w",stdout);
101     init();
102     solve();
103     return 0;
104 }