/** * 小明的旅途中需要经过一个国家。这个国家有n个城市,编号为1到n。小明会从1号城市进入,目标是从n号城市出去(即要从1号城市到达n号城市)。有m条双向道路连接这n个城市,每条道路的长度都是1,并且都有一个过路费(是[1,100000]之间的整数)。当小明在一号城市时,他可以预先花费X的费用办一张特权卡,他可以获得所有过路费不超过X的道路的通行权(而其他道路无法通过)。小明一天最多只能走k长度的路,他想知道如果他想在一天之内从1号城市走到n号城市,他最少需要花费多少来办特权卡,即求X的最小值? * <p> * <p> * <p> * 输入描述 * 第一行是3个整数n,m,k,分别表示城市数,道路数和小明一天最多能走的长度。 * <p> * 第二行m个整数,分别为u1, u2, …, um,分别表示第i条道路的一个端点。 * <p> * 第三行m个整数,分别为v1, v2, …, vm,分别表示第i条道路的另一个端点。 * <p> * 第四行m个整数,分别为w1, w2, …, wm,分别表示第i条道路的过路费。 * <p> * 数字间两两有空格隔开。数据保证一定存在解。 * <p> * 输出描述 * 一行一个整数,表示X的最小值。 * <p> * <p> * 样例输入 * 5 6 3 * 1 1 2 3 3 4 * 2 5 3 4 5 5 * 1 3 1 2 1 1 * 样例输出 * 1 * <p> * 提示 * n<=100000,m<=200000,1<=w<=100000。 */public class 最小过路费 {    public static void main(String[] args) {        Set<Long> st = new HashSet<>(1 << 15);        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int m = sc.nextInt();        int k = sc.nextInt();        int[] u = new int[m + 1];        int[] v = new int[m + 1];        int[] w = new int[m + 1];        for (int i = 1; i <= m; i++) {            u[i] = sc.nextInt();        }        for (int i = 1; i <= m; i++) {            v[i] = sc.nextInt();        }        for (int i = 1; i <= m; i++) {            w[i] = sc.nextInt();        }        List<int[]>[] g = new List[n + 1];        Arrays.setAll(g, p -> new ArrayList<>(64));        for (int i = 1; i <= m; i++) {            g[u[i]].add(new int[]{v[i], w[i]});            if (u[i] != 1)                g[v[i]].add(new int[]{u[i], w[i]});        }        //{点,状态,step}  mask的存w,不可以用相同的权访问同一个结点        PriorityQueue<long[]> q = new PriorityQueue<>(                100000,                Comparator.comparingLong(i -> i[1]));        q.offer(new long[]{1, 0, 0});        st.add(1L);        while (!q.isEmpty()) {            long[] p = q.poll();            int x = (int) p[0];            long wx = p[1];            long s = p[2];            if (x == n && s <= k) {                System.out.println(wx);                return;            }            for (int[] d : g[x]) {                long mask = Math.max(d[1], wx);                long step = s + 1;                // 如果已经以相同的状态访问过该结点 就不用再次扩展                // 如果当前扩展的结点的权 ws >= res, 直接剪枝。x的值不可能比res更小了                if (!st.contains(mask << 20 | d[0]) && step <= k) {                    st.add(mask << 20 | d[0]);                    q.offer(new long[]{d[0], mask, step});                }            }        }        System.out.println(-1);    }} public class 镜像 {    /**   值得注意的点:复制后会出现很多循环子段,我们只需要在最小循环子段中找答案,否则会复杂度过高     * 已知一个序列的生成方式如下:     * <p>     * • 序列生成需要一个基础序列A,这个序列由n个 不大于100的数字组成,同时给定镜像复制次数m。     * <p>     * • 然后对于A进行m次镜像复制,例如序列A={1,2,3},则一次镜像复制后得到的序列是{1,2,3,3,2,1},两次镜像复制得到的序列是B={1,2,3,3,2,1,1,2,3,3,2,1} 。     * <p>     * 现在给出你生成一个序列所需要的参数,请你计算该序列的第k位是多少。     * <p>     * <p>     * <p>     * 输入描述     * 输入第一行包含三个整数n,m,k,含义如题所示。(1<=n<=100,1<=m<=60,1<=k<=1e18,部分数据k<10000)     * <p>     * 输入第二行包含n个正整数,每个正整数都不大于100,表示基础序列A。     * <p>     * 数字间有空格隔开     * <p>     * 输出描述     * 输出仅包含一个正整数,即序列第k位的数字。     * <p>     * <p>     * 样例输入     * 3 3 10     * 1 2 3     * 样例输出     * 3     */    public static void main(String[] args) {        // write your code here        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int m = sc.nextInt();        int k = sc.nextInt();        int[] a = new int[(n << 1) + 1];        for (int i = 1; i <= n; i++) {            a[i] = sc.nextInt();            a[(n << 1) - i + 1] = a[i];        }        k = k % (n << 1);        System.out.println(a[k]);    }}            
点赞 0
评论 1
全部评论

相关推荐

机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务