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