滴滴9.13笔试
岗位是安卓开发。由于不太会图相关的算法，所以都是用BFS解决的，运气好都A了。
第一题，修桥。
import java.util.*;
public class Q1_20200913 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int times = sc.nextInt();
for (int o = 0; o < times; o++) {
int n = sc.nextInt();
int m = sc.nextInt();
int limit = sc.nextInt();
List<Integer>[] bridges = new List[n + 1];
for (int i = 0; i < n + 1; i++) {
bridges[i] = new LinkedList<>();
}
for (int i = 0; i < m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
int cost = sc.nextInt();
if (cost <= limit) {
bridges[l].add(r);
bridges[r].add(l);
}
}
HashSet<Integer> arrived = new HashSet<>();
Deque<Integer> list = new LinkedList<>(bridges[1]);
while (!list.isEmpty()) {
int cur = list.poll();
arrived.add(cur);
for (Integer i : bridges[cur]) {
if (!arrived.contains(i)) {
arrived.add(i);
list.add(i);
}
}
}
if (arrived.size() == n) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
}
import java.util.*;
public class Q2_20200913 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
List<int[]>[] ways = new List[n + 1];
for (int i = 0; i < n + 1; i++) {
ways[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
int cost = sc.nextInt();
int[] lr = {r, cost};
ways[l].add(lr);
int[] rl = {l, cost};
ways[r].add(rl);
}
int start = sc.nextInt();
int tar = sc.nextInt();
String time = sc.next();
int[] arrived = new int[n + 1];
Arrays.fill(arrived, Integer.MAX_VALUE);
Deque<int[]> list = new LinkedList<>();
list.add(new int[]{start, 0});
while (!list.isEmpty()) {
int[] cur = list.poll();
int pos = cur[0];
int cost = cur[1];
if (cost < arrived[pos]) {
arrived[pos] = cost;
for (int[] arr : ways[pos]) {
if (arr[1] + cost < arrived[arr[0]]) {
list.add(new int[]{arr[0], arr[1] + cost});
}
}
}
}
int res = arrived[tar];
String out = help(res, time);
System.out.println(out);
}
}
static int[] months = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
public static String help(int res, String time) {
String[] temp = time.split("\\.");
int month = Integer.parseInt(temp[0]);
temp = temp[1].split("/");
int day = Integer.parseInt(temp[0]);
int hour = Integer.parseInt(temp[1]);
hour += res;
if (hour >= 24) {
day += hour / 24;
hour = hour % 24;
}
while (day > months[month]) {
day -= months[month];
month++;
}
StringBuilder arrive = new StringBuilder();
arrive.append(month).append(".")
.append(day).append("/").append(hour);
return arrive.toString();
}
}
