洛谷 P1951 收費站_NOI導刊2009提高（2） 最短路+二分
目錄
題面
題目連結
ofollow,noindex" target="_blank">P1951 收費站_NOI導刊2009提高（2）
其實還有一道雙倍經驗
題目描述
在某個遙遠的國家裡，有n個城市。編號為1，2，3，…,n。
這個國家的政府修建了m條雙向的公路。每條公路連線著兩個城市。沿著某條公路，開車從一個城市到另一個城市，需要花費一定的汽油。
開車每經過一個城市，都會被收取一定的費用（包括起點和終點城市）。所有的收費站都在城市中，在城市間的公路上沒有任何的收費站。
小紅現在要開車從城市u到城市v（1 $ \leq u,v \leq n $ ）。她的車最多可以裝下 $ s $ 升的汽油。在出發的時候，車的油箱是滿的，並且她在路上不想加油。
在路上，每經過一個城市，她都要交一定的費用。如果某次交的費用比較多，她的心情就會變得很糟。所以她想知道，在她能到達目的地的前提下，她交的費用中最多的一次最少是多少。這個問題對於她來說太難了，於是她找到了聰明的你，你能幫幫她嗎？
輸入輸出格式
輸入格式
第一行5個正整數， $ n,m,u,v,s $ ，分別表示有 $ n $ 個城市， $ m $ 條公路，從城市 $ u $ 到城市 $ v $ ，車的油箱的容量為 $ s $ 升。
接下來的有 $ n $ 行，每行1個整數， $ f_i $ 表示經過城市 $ i $ ，需要交費 $ f_i $ 元。
再接下來有 $ m $ 行，每行3個正整數，$ a_i,b_i,c_i (1 \leq a_i,b_i \leq n) $ ,表示城市 $ a_i $ 和城市 $ b_i $ 之間有一條公路，如果從城市 $ a_i $ 到城市 $ b_i $ ，或者從城市 $ b_i $ 到城市 $ a_i $ ，需要 $ c_i $ 升的汽油。
輸出格式
僅一個整數，表示小紅交費最多的一次的最小值。
如果她無法到達城市 $ v $ ，輸出-1
輸入輸出樣例
輸入樣例：
輸出樣例：
說明
【資料規模】
對於60%的資料，滿足 $ n \leq 200,m \leq 10000,s \leq 200 $
對於100%的資料，滿足 $ n \leq 10000,m \leq 50000,s \leq 1000000000 $
對於100%的資料，滿足 $ c_i \leq 1000000000,f_i \leq1000000000, $ 可能有兩條邊連線著相同的城市。
【時空限制】
1000ms,128M
思路
首先看題目的問法，求最大值的最小 ，可以考慮到二分答案
首先假定當答案是x，那麼他肯定要滿足如果不經過交費超過x的點，跑一遍從u到v的最短路一定小於總油量
於是可以根據此多次跑最短路了
AC程式碼
#include<bits/stdc++.h>
const int maxn=10010;
const int maxm=50010;
using namespace std;
int n,m,st,ed,W,wt[maxn];
int tot,to[maxm<<1],nxt[maxm<<1],head[maxn],len[maxm<<1];
int l,r,dis[maxn];
priority_queue< pair<int,int> > q;
bool vis[maxn],b;
void Dijkstra(int mx)
{
for(int i=1;i<=n;i++) dis[i]=INT_MAX/2;
for(int i=1;i<=n;i++) vis[i]=false;
dis[st]=0;
q.push(make_pair(0,st));
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(wt[v]>mx) continue;
if(dis[u]+len[i]<dis[v])
{
dis[v]=dis[u]+len[i];
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&st,&ed,&W);
for(int i=1;i<=n;i++)
{
scanf("%d",&wt[i]);
r=max(r,wt[i]);
}
for(int i=1;i<=m;i++)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
to[++tot]=v;nxt[tot]=head[u];len[tot]=w;head[u]=tot;
to[++tot]=u;nxt[tot]=head[v];len[tot]=w;head[v]=tot;
}
l=max(wt[st],wt[ed]);
do ///不要while! 否則如果wt[st]和wt[ed]相等就不能進迴圈了
{
int mid=(l+r)>>1;
Dijkstra(mid);
if(dis[ed]>W) l=mid+1;
else r=mid,b=true;
}while(l<r);
if(b) printf("%d",r);
else printf("-1");
return 0;
}
總結
這題第一遍做只得了80分，因為寫的是while而不是do while，這個錯很隱蔽。。如果l=0肯定就不會出這種情況了（吧）（所以我想說的是這樣定左邊界很靈性）
另外，判斷是否可到終點的時候，放在r這一邊也是一時想到（感謝Uranus巨巨）