例題：
【題目描述】在某個遙遠的國家裏，有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 8856102 1 22 4 11 3 43 4 3【輸出樣例1】8【輸入樣例2】4 4 2 3 3856102 1 22 4 11 3 43 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 }
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 }
