Description

在某個遙遠的國家里，有n個城市。編號為1，2，3，……，n。 這個國家的政府修建了m條雙向的公路。每條公路連接著兩個城市。沿著某條公路，開車從一個城市到另一個城市，需要花費一定的汽油。開車每經(jīng)過一個城市，都會被收取一定的費用（包括起點和終點城市）。所有的收費站都在城市中，在城市間的公路上沒有任何的收費站。小紅現(xiàn)在要開車從城市u到城市v(1<=u，v<=n)。她的車最多可以裝下s升的汽油。在出發(fā)的時候，車的油箱是滿的，并且她在路上不想加油。在路上，每經(jīng)過一個城市，她要交一定的費用。如果她某次交的費用比較多，她的心情就會變得很糟。所以她想知道，在她能到達目的地的前提下，她交的費用中最多的一次最少是多少。這個問題對于她來說太難了，于是她找到了聰明的你，你能幫幫她嗎？

Input

第一行5個正整數(shù)，n，m，u，v，s。分別表示有n個城市，m條公路，從城市u到城市v，車的油箱的容量為s升。接下來有n行，每行1個正整數(shù)，fi。表示經(jīng)過城市i，需要交費fi元。 再接下來有m行，每行3個正整數(shù)，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之間有一條公路，如果從城市ai到城市bi，或者從城市bi到城市ai，需要用ci升汽油。

Output

僅一個整數(shù)，表示小紅交費最多的一次的最小值。 如果她無法到達城市v，輸出-1。

Sample Input

輸入樣例1

4 4 2 3 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

輸入樣例2

4 4 2 3 3
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

Sample Output

輸出樣例1

8

輸出樣例2

-1

Data Constraint

數(shù)據(jù)規(guī)模 對于60%的數(shù)據(jù)，滿足n<=200，m<=19900，s<=200，沒有一條邊連接著兩個相同的城市。
對于100%的數(shù)據(jù)，滿足n<=10000，m<=50000，s<=1000000000，可能有兩條邊連接著相同的城市。
對于100%的數(shù)據(jù)，滿足ci<=1000000000，fi<=1000000000

Solution

• 這題又是套路——雙條件問題，果斷轉(zhuǎn)換成 二分+判斷性問題！

• 考慮二分答案，即得到一個城市花費的上限

• 之后，以起點進行一次 SPFA ，中途不能遍歷超過上限的點

• 最后看終點是否能被遍歷到，再修改二分上下界即可！

• 然而心機出題人的數(shù)據(jù)竟然能卡掉強悍的 SPFA，時間略微上溢

• 于是考慮使用堆維護 SPFA 中的節(jié)點，使其遠者優(yōu)先，提高效率

• 注： 為了方便，以下標程中使用 C++ 優(yōu)先隊列并重載運算符。

Code

#include<cstdio> #include<queue> using namespace std; const int N=10001; struct data {int node,pay; }que[N]; int tot,n,m,u,v,s; long long sum,dis[N]; int f[N]; int first[N],next[N*10],en[N*10],w[N*10]; bool bz[N]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } struct cmp {bool operator()(int x,int y){return dis[x]>dis[y];} }; inline bool spfa(int lim) {if(f[u]>lim || f[v]>lim) return false;priority_queue <int,vector<int>,cmp> que;for(int i=1;i<=n;i++) dis[i]=sum;dis[u]=0;que.push(u);while(!que.empty()){int now=que.top();que.pop();bz[now]=false;for(int i=first[now];i;i=next[i]){if(f[en[i]]>lim) continue;if(dis[now]+w[i]<dis[en[i]]){dis[en[i]]=dis[now]+w[i];if(!bz[en[i]]){bz[en[i]]=true;que.push(en[i]);}}}}return dis[v]<=s; } int main() {n=read(),m=read(),u=read(),v=read(),s=read();int l=1e9,r=0;for(int i=1;i<=n;i++){f[i]=read();if(f[i]>r) r=f[i]; elseif(f[i]<l) l=f[i];}for(int i=1;i<=m;i++){int x=read(),y=read(),z=read();if(x==y) continue;sum+=z;insert(x,y,z);insert(y,x,z);}int ans=-1;while(l<=r){int mid=(l+r)>>1;if(spfa(mid)){ans=mid;r=mid-1; }else l=mid+1;}printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 1251. 收费站的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。