[JZOI]1251.收费站[二分][最短路]

mac2024-10-01  22

Description

在某个遥远的国家里,有n个城市。编号为1,2,3,……,n。 这个国家的政府修建了m条双向的公路。每条公路连接着两个城市。沿着某条公路,开车从一个城市到另一个城市,需要花费一定的汽油。 开车每经过一个城市,都会被收取一定的费用(包括起点和终点城市)。所有的收费站都在城市中,在城市间的公路上没有任何的收费站。 小红现在要开车从城市u到城市v(1<=u,v<=n)。她的车最多可以装下s升的汽油。在出发的时候,车的油箱是满的,并且她在路上不想加油。 在路上,每经过一个城市,她要交一定的费用。如果她某次交的费用比较多,她的心情就会变得很糟。所以她想知道,在她能到达目的地的前提下,她交的费用中最多的一次最少是多少。这个问题对于她来说太难了,于是她找到了聪明的你,你能帮帮她吗?

Input

第一行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升汽油。

Output

仅一个整数,表示小红交费最多的一次的最小值。 如果她无法到达城市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

数据规模 对于60%的数据,满足n<=200,m<=19900,s<=200,没有一条边连接着两个相同的城市。 对于100%的数据,满足n<=10000,m<=50000,s<=1000000000,可能有两条边连接着相同的城市。 对于100%的数据,满足ci<=1000000000,fi<=1000000000

Analysis

有n个带权点,m条带权边的无向图。 n ∈ [ 1 , 10000 ] , m ∈ [ 1 , 50000 ] n \in [1,10000],m\in[1,50000] n[1,10000],m[1,50000]从点u出发到v,经过的所有点点权不得超过一个数,且最短路长度不得超过s输出这个数的最大值 对于这种最大值问题,考虑二分答案。

Solution

计算出最大点权作为二分上界,所以答案范围在[1,maxfee]的区间内。 因此我们二分枚举答案检验是否合法:

//二分答案 ll ll = 1,rr = maxfee,ans = -1,mid; while(ll<=rr) { mid = (ll+rr)>>1; if(dij(u,mid))//检验是否合法 { ans = mid; rr = mid-1; } else ll = mid+1; }

二分后使用最短路算法,更新的时候判断 目标点 的点权是否合法,若不合法则不能用于更新最短路。 那么我们需要对更新的判断语句做一点调整。 以dijkstra算法为例进行对比:

if(!vis[v] && dis[v] > dis[u] + map[u][v])//以基点更新最短路 dis[v] = dis[u] + map[u][v];//这里使用了简朴的写法,仅仅用于对比

那么我们添加限定条件后,只是简单地变为

if(!vis[v] && cost[v] <= ans && dis[v] > dis[u] + map[u][v]) dis[v] = dis[u] + map[u][v];

这个ans即我们正在验证的答案。最后求完最短路,判定答案是否合法就简单了:

if(dis[v] > s) return false;

因为dis数组初始化为无穷大,所以无论是未访问到的情况还是超过给出最短路限定长度s的情况都能这样排掉。 到此,本题就结束了。 但其实,还有最后一个点,卡了我几十分钟的一个神奇问题(当然是我太菜了) 还需要判断起点的点权是否合法(捂脸)

if(cost[start] > maxf) return false;

就这么一行……

Code

链式前向星存图根优化dijkstra求最短路二分查找答案 #include <cstdio> #include <cstring> #include <queue> typedef long long ll; using namespace std; //functions inline void add(const ll&,const ll&,const ll&); void read(ll&); ll init(); bool dij(ll,ll); //end struct node { ll d,to,next; node(ll q,ll w,ll e) {to=q,next=w,d=e;} node(){} }lines[100010]; ll head[10010]; ll cost[10010]; ll dis[10010]; ll n,m,u,v,s; int main() { ll maxfee = init();//初始化 //二分答案 ll ll = 1,rr = maxfee,ans = -1,mid; while(ll<=rr) { mid = (ll+rr)>>1; if(dij(u,mid)) { ans = mid; rr = mid-1; } else ll = mid+1; } printf("%d",ans); return 0; } ll init() { read(n);read(m);read(u);read(v);read(s); ll maxfee = 0; for(int i = 1;i<=n;++i) { read(cost[i]); if(cost[i] > maxfee) maxfee = cost[i]; } ll ai,bi,ci; for(int i = 1;i<=m;++i) { read(ai); read(bi); read(ci); add(ai,bi,ci); add(bi,ai,ci); } return maxfee; } void read(ll &r) { static char c;r = 0; for(c=getchar();c>'9'||c<'0';c=getchar()); for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+c-48,c=getchar()); } inline void add(const ll &x,const ll &y,const ll &d) { static ll tot = 0; lines[++tot] = node(y,head[x],d); head[x] = tot; } ll vis[10010]; struct Point { ll num,dis; bool operator<(const Point &b) const { return dis>b.dis; } Point(){} Point(ll an,ll ad){num = an,dis = ad;} }; priority_queue<Point> q; bool dij(ll start,ll maxf) { while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); memset(dis,126,sizeof(dis)); if(cost[start] > maxf) return false; dis[start] = 0; q.push(Point(start,0)); int u; while(!q.empty()) { u = q.top().num; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int p = head[u];p;p=lines[p].next) { if(!vis[lines[p].to] \ && cost[lines[p].to] <= maxf \ && dis[lines[p].to] > dis[u] + lines[p].d) { dis[lines[p].to] = dis[u]+lines[p].d; q.push(Point(lines[p].to,dis[lines[p].to])); } } } if(dis[v] > s) return false; return true; }
最新回复(0)