G. Rudolf and Subway：

题目大意：

        

思路解析：

        这道题很容易看出是一个最短路的图论问题，但是Java普通最短路常数有点高会被卡。

        因为他是地铁线路，线路一定是一直连着的，不会中间断开，那我们可以从一个颜色线路上的站点到的任意其他站点，那我们就可以将整个图分为多个颜色块。从颜色块加速状态转移的过程，转移就变为了如果我们当前在一个站点上，那就选择一个这个站点能去的线路，如果当前在线路上，就选择当前在这个线路的那个地点停下。

 代码实现：

        

import java.util.*;
import java.io.*;public class Main {static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int t = Integer.parseInt(br.readLine());while (t-- > 0) {solve(br);}w.flush();w.close();}static void solve(BufferedReader br) throws IOException {StringTokenizer st = new StringTokenizer(br.readLine());int n = Integer.parseInt(st.nextToken());int m = Integer.parseInt(st.nextToken());Vector<Integer> a = new Vector<>();HashMap<Integer, Integer> map = new HashMap<>();int[][] edges = new int[m][3];for (int i = 0; i < m; i++) {st = new StringTokenizer(br.readLine());edges[i][0] = Integer.parseInt(st.nextToken()) - 1;edges[i][1] = Integer.parseInt(st.nextToken()) - 1;edges[i][2] = Integer.parseInt(st.nextToken());a.add(edges[i][2]);}int k = 0;for (int i = 0; i < a.size(); i++) {int num = a.get(i);if (!map.containsKey(num)){map.put(num, n + k + 1);k++;}}st = new StringTokenizer(br.readLine());int b = Integer.parseInt(st.nextToken()) - 1;int e = Integer.parseInt(st.nextToken()) - 1;LinkedList<Integer>[] list = new LinkedList[n + k + 1];for (int i = 0; i < n + k + 1; i++) {list[i] = new LinkedList<>();}for (int i = 0; i < m; i++) {int u = edges[i][0];int v = edges[i][1];int c = map.get(edges[i][2]);list[u].add(c);list[v].add(c);list[c].add(u);list[c].add(v);}LinkedList<Integer> q = new LinkedList<>();q.add(b);int[] dp = new int[n+k+1];Arrays.fill(dp, (int) 1e9);dp[b] = 0;while (!q.isEmpty()){int x = q.poll();if (x == e) break;for (Integer y : list[x]) {if (dp[y] > dp[x] + 1){dp[y] = dp[x] + 1;q.addLast(y);}}}System.out.println(dp[e] / 2);}static class Pair<T1, T2> {T1 first;T2 second;public Pair(T1 first, T2 second) {this.first = first;this.second = second;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (!(o instanceof Pair)) return false;Pair<?, ?> pair = (Pair<?, ?>) o;return Objects.equals(first, pair.first) &&Objects.equals(second, pair.second);}@Overridepublic int hashCode() {return Objects.hash(first, second);}}
}