算法分析

单源最短路 + 二分

题目描述到有k条边可以免费升级，因此只需要求1~N的所有路径中第k + 1大的值的最小值，是最大最小值模型，因此可以使用二分求解

对于区间[0,1000001]中的某一个点x：

• 1、check(x)函数表示:从1走到N，最少经过的长度大于x的边数的数量是否小于等于k，若是则返回true，否则返回false

• 2、求出从1到N最少经过几条长度大于x的边
  可以分类成：

  • 如果边大于x，则边权看成1

  • 如果边长小于等于x，则边权看成0

注意：

• 1、初始l = 0，r = 1000001的原因是：如果1号点到n号点是不连通的，最后二分出来的值一定是1000001，表示无解

• 2、对于只有两种边权是0,1可以使用双端队列求解，下面使用的是堆优化版Dijkstra

时间复杂度 $O(mlogn * logL)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main{
    static int N = 1010;
    static int M = 10010 * 2;
    static int m;
    static int n;
    static int k;
    static int INF = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];
    static int[] id = new int[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int ans = INF;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static boolean check(int x)
    {
        PriorityQueue<PIIs> q = new PriorityQueue<PIIs>();
        Arrays.fill(st,false);
        Arrays.fill(dist, INF);
        q.add(new PIIs(0,1));
        dist[1] = 0;

        while(!q.isEmpty())
        {
            PIIs p = q.poll();
            int t = p.second;
            int distance = p.first;

            if(st[t]) continue;
            st[t] = true;

            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                //若权值大于x则权值看成1
                if(w[i] > x)
                {
                    dist[j] = Math.min(dist[j], distance + 1);
                    q.add(new PIIs(dist[j],j));
                }
                //若权值小于等于x则权值看成0
                else
                {
                    dist[j] = Math.min(dist[j], distance);
                    q.add(new PIIs(dist[j],j));
                }
            }
        }

        if(dist[n] <= k) return true;
        return false;

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        k = Integer.parseInt(s1[2]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a,b,c);
            add(b,a,c);
        }
        int l = 0,r = 1000001;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(r == 1000001) System.out.println("-1");
        else System.out.println(r);
    }
}
class PIIs implements Comparable<PIIs> 
{
    public int first;
    public int second;
    public PIIs(int first,int second)
    {
        this.first = first;
        this.second = second;
    }
    @Override
    public int compareTo(PIIs o) {
        // TODO 自动生成的方法存根
        return Integer.compare(first, o.first);
    }
}

双端队列bfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    static int N = 1010, M = 10010 * 2, INF = 0x3f3f3f3f;
    static int n, m, k;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx = 0;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //最少经过 值 > x的边数 小于等于k
    static boolean check(int x)
    {
        Arrays.fill(dist, INF);
        Arrays.fill(st, false);
        Deque<Integer> q = new LinkedList<Integer>();
        q.addLast(1);
        dist[1] = 0;
        while(!q.isEmpty())
        {
            int t = q.pollFirst();
            if(st[t]) continue;
            st[t] = true;
            for(int i = h[t]; i != -1;i = ne[i])
            {
                int j = e[i];

                int u = w[i] > x ? 1 : 0;//判断该权值是1还是0

                if(dist[j] > dist[t] + u)
                {
                    dist[j] = dist[t] + u;
                    if(u == 0) q.addFirst(j);
                    else q.addLast(j);
                }
            }
        }
        return dist[n] <= k;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        k = Integer.parseInt(s1[2]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a, b, c);
            add(b, a, c);
        }
        //求第k + 1条大的最小值
        int l = 0, r = 1000001;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(check(l)) System.out.println(l);
        else System.out.println(-1);
    }
}