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
;
inline void add(const ll
&,const ll
&,const ll
&);
void read(ll
&);
ll
init();
bool dij(ll
,ll
);
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;
}
