时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回和上上回里我们知道Nettle在玩《艦これ》，Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。在这个游戏里面，海域是N个战略点(编号1..N)组成，如下图所示
其中红色的点表示有敌人驻扎，猫头像的的点表示该地图敌军主力舰队(boss)的驻扎点，虚线表示各个战略点之间的航线(无向边)。在游戏中要从一个战略点到相邻战略点需要满足一定的条件，即需要舰队的索敌值大于等于这两点之间航线的索敌值需求。由于提高索敌值需要将攻击机、轰炸机换成侦察机，舰队索敌值越高，也就意味着舰队的战力越低。另外在每一个战略点会发生一次战斗，需要消耗1/K的燃料和子弹。必须在燃料和子弹未用完的情况下进入boss点才能与boss进行战斗，所以舰队最多只能走过K条航路。现在Nettle想要以最高的战力来进攻boss点，所以他希望能够找出一条从起始点(编号为1的点)到boss点的航路，使得舰队需要达到的索敌值最低，并且有剩余的燃料和子弹。特别说明：两个战略点之间可能不止一条航线，两个相邻战略点之间可能不止一条航线。保证至少存在一条路径能在燃料子弹用完前到达boss点。
输入
第1行：4个整数N,M,K,T。N表示战略点数量，M表示航线数量，K表示最多能经过的航路，T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000第2..M+1行：3个整数u,v,w，表示战略点u,v之间存在航路，w表示该航路需求的索敌值，1≤w≤1,000,000。
输出
第1行：一个整数，表示舰队需要的最小索敌值。
样例输入5 6 2 51 2 31 3 21 4 42 5 23 5 54 5 3样例输出3
【Java代码】
import java.util.HashMap;import java.util.ArrayList;import java.util.Iterator;import java.util.LinkedList;import java.util.Scanner;public class Main {public static HashMap<Integer, ArrayList<Integer>> map; // < from, List<10000 * w + to> >public static int N, M, K, T;public static boolean bfs(int myw) {boolean[] visit = new boolean[N + 1];LinkedList<Integer> queue = new LinkedList<Integer>();queue.offer(1);visit[1] = true;queue.offer(-1);int deep = 0;while (!queue.isEmpty() && deep < K) {int cur = queue.poll();if (cur == -1) {if (!queue.isEmpty()) {deep++;queue.offer(-1);continue;} else {break;}}if (map.containsKey(cur)) {ArrayList<Integer> list = map.get(cur);Iterator<Integer> it = list.iterator();while (it.hasNext()) {int tmp = it.next();int v = tmp % 10001;int w = tmp / 10001;if (!visit[v] && w <= myw) {if (v == T) return true;queue.offer(v);visit[v] = true;}}}}return false;}public static void main(String[] args) {Scanner in = new Scanner(System.in);N = in.nextInt();M = in.nextInt();K = in.nextInt();T = in.nextInt();HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();Main.map = map;int high = Integer.MIN_VALUE;int low = Integer.MAX_VALUE;for (int i = 0; i < M; i++) {int u = in.nextInt();int v = in.nextInt();int w = in.nextInt();if (!map.containsKey(u)) {ArrayList<Integer> vw = new ArrayList<Integer>();vw.add(10001 * w + v);map.put(u, vw);} else {ArrayList<Integer> vw = map.get(u);vw.add(10001 * w + v);}if (!map.containsKey(v)) {ArrayList<Integer> uw = new ArrayList<Integer>();uw.add(10001 * w + u);map.put(v, uw);} else {ArrayList<Integer> uw = map.get(v);uw.add(10001 * w + u);}high = Math.max(high, w);low = Math.min(low, w);}while (low + 1 < high) {int mid = (low + high) / 2;if (bfs(mid)) {high = mid;} else {low = mid;}}System.out.println(high);}}
【说明】
这道题得用map来存储一个点可以到达得点，，用二维邻接矩阵会超时。
免责声明：题目来源于hihoCoder.com，如有侵权，请联系博主删帖。
只有坚韧不拔向着目标奋进，成功后将在不远处等待着你的到来。
