【图论杂题】：F. cost [dijkstra+二分答案]

题目：

团队链接：cost

题面：

给定一张$n$个点$m$条边的带点权带边权无向图
要求找一条从点$u$到点$v$的路径，满足：

• 路径上的边权和 $<=s$
• 路径上点权的最大值最小

求点权的最大值
范围：$n<=10000,m<=50000,s<=1e9$

样例：

输入：

5 5 4 3 30
206
2312
8463
3442
6677
1 4 3
5 3 6
2 3 7
4 2 2
4 2 3

输出：

8463

题解：

一看最大值最小，怎么办，，，二分答案？ 二分答案！
对于一个二分值x，将点权<=x的点和这些点之间的边加入图中，再从S到T跑最短路（我写的dijkstra得堆优化），要是dis[T]<=s,那x就是合法的。

代码：

#include<bits/stdc++.h>
#define pii pair<int ,int> 
#define fir first 
#define sec second 
using namespace std;
inline int read()
{
    int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int ocean=1e9+7;
const int sea=5e4+7;
const int pool=1e4+7;
struct see{
    int ver,x,next,edge;}e[sea<<1];
int n,m,S,T,W,tot;
int w[sea],last[sea<<1],dis[pool];
priority_queue<pii,vector<pii>,greater<pii> >Q;
void add(int x,int y,int z){
    e[++tot].x=x;e[tot].ver=y;e[tot].edge=z;e[tot].next=last[x],last[x]=tot;}
bool check(int x)//dijkstra+堆优化
{
    if(w[S]>x||w[T]>x) return 0;for(int i=1;i<=n;i++) dis[i]=ocean;dis[S]=0;Q.push(make_pair(0,S));while(!Q.empty()){
    pii u=Q.top(); Q.pop();if(dis[u.sec]<u.fir) continue;for(int i=last[u.sec];i;i=e[i].next){
    int y=e[i].ver,z=e[i].edge;if(w[y]<=x&&dis[y]>u.fir+z){
    dis[y]=u.fir+z;Q.push(make_pair(dis[y],y));		}}}return dis[T]<=W;
}
int main()
{
    n=read(); m=read(); S=read(); T=read();W=read();for(int i=1;i<=n;i++) w[i]=read();for(int i=1;i<=m;i++){
    int x=read(),y=read(),z=read();add(x,y,z); add(y,x,z);}int l=1,r=ocean,ans=-1;//二分答案，二分点权while(l<=r){
    int  mid=(l+r)/2;if(check(mid)) ans=mid,r=mid-1;else l=mid+1;}printf("%d\n",ans);return 0;
}

Continue……