/** * 小明的旅途中需要经过一个国家。这个国家有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]); }}