让最大值最小,二分最大值,大于最大值的边权置1,最短路的长度就是免费升级线路的数量
import java.io.*;
import java.util.*;
public class Main{
static int N = 1010,M = 2*100010;
static int[] h = new int[N],e = new int[M],ne = new int[M],
w = new int[M],dist = new int[M];
static int idx = 0,n,m,k;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
Arrays.fill(h,-1);
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
for(int i = 0;i<m;i++){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a,b,c);
add(b,a,c);
}
int l = 0,r = (int)1e6+1;
while(l<r){
int mid = l+r>>1;
if(check(mid)) r = mid;
else l = mid+1;
}
if(r == (int)1e6+1) System.out.println(-1);
else System.out.println(r);
}
public static boolean check(int x){
Deque<Integer> dq = new LinkedList<>();
dq.add(1);
Arrays.fill(dist,0x3f3f3f3f);
dist[1] = 0;
while(!dq.isEmpty()){
int t = dq.pollFirst();
for(int i = h[t];i!=-1;i = ne[i]){
int j = e[i];
int u = 0;
if(w[i]>x) u = 1;
if(dist[j]>dist[t]+u){
dist[j] = dist[t]+u;
if(u == 1) dq.addLast(j);
else dq.addFirst(j);
}
}
}
return dist[n]<=k;
}
public static void add(int a,int b,int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
}
让最大值最小,首先想到的是二分,二分就要满足答案左边和右边各自的性质不一样
我们可以二分最大值,check一下以当前值作为最大值能否满足要求
import java.io.*;
import java.util.*;
public class Main{
static int N = 10010,M = 100010;
static int[] h = new int[N],e = new int[M],ne = new int[M],
blood = new int[M],cost = new int[N],dis = new int[N];
static boolean[] st = new boolean[N];
static int n,m,b,idx = 0,INF = 0x3f3f3f3f;
public static void main(String[] args)throws IOException{
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
Arrays.fill(h,-1);
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
b = Integer.parseInt(s[2]);
for(int i = 1;i<=n;i++)
cost[i] = Integer.parseInt(br.readLine());
for(int i = 1;i<=m;i++){
s = br.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
int c = Integer.parseInt(s[2]);
add(a,b,c);
add(b,a,c);
}
int ll = 0,rr = (int)1e9+1;
//范围+1,如果是最大值的范围就表示不可能到达
while(ll<rr){
int mid = ll+rr>>1;
if(check(mid)) rr = mid;
else ll = mid+1;
}
if(rr == (int)1e9+1) System.out.println("AFK");
else System.out.println(rr);
}
public static boolean check(int u){
if(cost[1]>u) return false;
Arrays.fill(dis,INF);
Arrays.fill(st,false);
PriorityQueue<int[]> pq
= new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
pq.add(new int[]{0,1});
while(!pq.isEmpty()){
int[] t = pq.poll();
int distance = t[0];
int ver = t[1];
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver];i!=-1;i = ne[i]){
int j = e[i];
if(dis[j]>distance+blood[i]&&cost[j]<=u){
dis[j] = distance+blood[i];
pq.add(new int[]{dis[j],j});
}
}
}
return dis[n]>b?false:true;
}
public static void add(int a,int b,int c){
e[idx] = b;
ne[idx] = h[a];
blood[idx] = c;
h[a] = idx++;
}
}