/**
* 小明的旅途中需要经过一个国家。这个国家有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]);
}
}
#小红书笔试#
投递海思半导体等公司10个岗位 >
查看11道真题和解析
