二分答案+堆优Dijkstra
- 这个题有些巧妙。
- 首先，因为要在油量耗完之前跑到终点，所以我们可以用最短路。只要从\(s\)出发到\(t\)，它的最短距离大于油量，我们就可以断定它一定走不通，直接输出\(-1\)。
- 然后因为要求最大值最小，所以考虑二分答案。用一个数组来储存点的值从大到小的排序，然后边界范围设置 : \(L\)为\(s\)和\(t\)的中较大的拿一个的排名,\(R\)为n。为什么\(L\)要这样设置呢？因为\(s\)和\(t\)是必经的点，所以它们一定要选，所以最小值只能设为它们之间较大的一个。
- 但是在存边的时候要注意，没有必要判重！！！因为两条路，他们连接的点可能一样，但是他们的距离不同，所以判重还会导致花费更多没必要的时间。我就是被说明给坑了。。。
- 上代码，有不清楚的代码里面尽量写明。
#include<bits/stdc++.h>
#define clean(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
using namespace std;
template<class T>il read(T &x) //快读
{
int f=1;char k=getchar();x=0;
for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
x*=f;
}
const int MAXN = 1e4+5,MAXM= 5e4+5;
int n,m,s,t,mx,u,v,d,num_edge,head[MAXN],val[MAXN],p[MAXN],dis[MAXN],l,r; //p数组用来存每个点的权值排序后的顺序
struct Edge{
int next,to,dis;
Edge(){}
Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
}edge[MAXM<<1]; //加边，无向边开两倍
il add_edge(int u,int v,int dis){
edge[++num_edge]=Edge(head[u],v,dis);head[u]=num_edge;
edge[++num_edge]=Edge(head[v],u,dis);head[v]=num_edge;
} //用结构体的生成函数写，方便又简洁
struct Node{
int dis,pos;
Node(){}
Node(int dis,int pos):dis(dis),pos(pos){}
bool operator <(const Node &t) const{
return dis>t.dis;
}
}; //用来跑Dijkstra，堆优要用
bool tr[MAXN]; //判断是否用这个点松弛过
il dijkstra(int lim){ //lim用来限制通过的点的最大权值
priority_queue<Node> q;q.push(Node(0,s));
clean(tr,0);clean(dis,0x3f);dis[s]=0; //初始化
while(!q.empty()){
Node tmp=q.top();q.pop();
ri pos=tmp.pos;
if(tr[pos]||val[pos]>lim) continue;
tr[pos]=true;
for(ri i=head[pos];i;i=edge[i].next){
if(dis[edge[i].to]>dis[pos]+edge[i].dis){
dis[edge[i].to]=dis[pos]+edge[i].dis;
if(!tr[edge[i].to]) q.push(Node(dis[edge[i].to],edge[i].to));
}
}
}
} //这个基本是堆优Dijkstra的模板，当然，在写法上可能有不同，不会的小伙伴可以去看一下 P4779 【模板】单源最短路径（标准版）
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m),read(s),read(t),read(mx); //读入
for(ri i=1;i<=n;i++) read(val[i]),p[i]=val[i];
for(ri i=1;i<=m;i++){
read(u),read(v),read(d);
if(d>mx) continue;
add_edge(u,v,d);
} //加边
sort(p+1,p+1+n); //给每个点的权值排序
dijkstra(p[n]); //先用最大的跑一遍，如果走不通，说明无解
if(dis[t]>mx){
printf("-1");
return 0;
}
for(ri i=1;i<=n;i++) if(p[i]==max(val[s],val[t])) {l=i;break;} //确定l的取值
r=n;
while(l<r){ //二分答案
dijkstra(p[mid]);
if(dis[t]>mx) l=mid+1;
else r=mid;
}
printf("%d",p[l]); //输出
return 0;
}