顺丰笔试
第一题，求最大得分和最大得分人数，以及他们的下标。按照题意求解，比较找最大值，输出即可。
第二题，无向图中求不舒服的路径。保证无环，边的权重也就是不舒服的程度，求a到b的路径中的不舒服的最大值。
比如：
5 4 3 // 节点数、边数、待求解路径个数 1 2 1 // 节点1 与 节点2 之间的不舒服程度为1 2 3 2 3 4 1 4 5 6 2 5 // 待求解 节点2 到 节点 5 4 1 5 3
输出：626
可以采用dfs来遍历。但昨天没做出来，通过18%。刚刚写了下，发现是回溯的时候边界条件的问题。记录下：
import java.util.*;
import java.util.Scanner;
public class TestC {
private static void insertData(Map<Integer, List<NodeT>> graph, int a, int b, int c){
if(!graph.containsKey(a)){
ArrayList<NodeT> lists = new ArrayList<>();
lists.add(new NodeT(b, c));
graph.put(a, lists);
}else{
List<NodeT> list = graph.get(a);
list.add(new NodeT(b, c));
graph.put(a, list);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] lines = scanner.nextLine().split(" ");
int vectorNumber = Integer.parseInt(lines[0]);
int edgeNumber = Integer.parseInt(lines[1]);
int questionNumber = Integer.parseInt(lines[2]);
Map<Integer, List<NodeT>> graph = new HashMap<>();
Map<String, Integer> weight = new HashMap<>();
for (int i = 0; i < edgeNumber; i++) {
String[] temp = scanner.nextLine().split(" ");
int a = Integer.parseInt(temp[0]);
int b = Integer.parseInt(temp[1]);
int c = Integer.parseInt(temp[2]);
insertData(graph, a, b, c);
insertData(graph, b, a, c);
weight.put(a+"to"+b, c);
weight.put(b+"to"+a, c);
}
List<Integer> resu = new ArrayList<>();
for (int i = 0; i < questionNumber; i++) {
String[] temp = scanner.nextLine().split(" ");
int a = Integer.parseInt(temp[0]);
int b = Integer.parseInt(temp[1]);
if(a == b){
resu.add(0);
}else{
List<Integer> res = new ArrayList<>();
List<List<Integer>> tempt = new ArrayList<>();
res.add(a);
boolean[] visited = new boolean[vectorNumber + 1];
visited[a] = true;
dfs(graph, a, b, res, visited, tempt);
res = tempt.get(0);
int w = 0;
for (int j = 1; j < res.size(); j++) {
w = Math.max(w, weight.get(res.get(j - 1) + "to" + res.get(j)));
}
resu.add(w);
}
}
for (Integer integer : resu) {
System.out.println(integer);
}
}
private static void dfs(Map<Integer, List<NodeT>> graph, int a, int b, List<Integer> temp, boolean[] visited, List<List<Integer>> res) {
List<NodeT> neighbors = graph.get(a);
for (NodeT node : neighbors) {
if(!visited[node.n]){
visited[node.n] = true;
temp.add(node.n);
if (node.n == b) {
res.add(new ArrayList<>(temp));
return;
}
dfs(graph, node.n, b, temp, visited, res);
temp.remove(temp.size() - 1);
visited[node.n] = false;
}
}
}
static class NodeT{
int n;
int weight;
public NodeT(int n, int weight){
this.n = n;
this.weight = weight;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
NodeT nodeT = (NodeT) o;
return n == nodeT.n &&
weight == nodeT.weight;
}
@Override
public int hashCode() {
return Objects.hash(n, weight);
}
}
/**
5 4 3
1 2 1
2 3 2
3 4 1
4 5 6
2 5
4 1
5 3
*/
} 
