【图论】C

一、题目描述

虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗。

但是草儿仍然很喜欢旅行，因为在旅途中会遇见很多人（白马王子，⁰），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……

眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input

• 输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
• 接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
• 接着的第T+1行有S个数，表示和草儿家相连的城市；
• 接着的第T+2行有D个数，表示草儿想去地方。

Output

• 输出草儿能去某个喜欢的城市的最短时间。

Input  
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
Sample Output
9

二、题解

方法一：多源转单源

• 因为草儿只能从与家相邻的城市出发，而去这些相邻城市是不花费前时间的，所以这些城市可以看成图中与起点相连而且边权为 0 的结点。
• 然后，就是跑最短路算法就行了。

重大发现：tot 是静态变量，如果在有多组数据测试的时候，一定要在没一组数据测试完毕之后将 tot 清零。

未知错误：总是得到一个 WA…

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{static int V, E, D;static Edge[] edges;static int[] dist, head;static boolean[] vis, inq;static int[] want;static int tot;static int INF = 0x3f3f3f3f;static int MAXN = 1000 + 50; static class Edge {int to, w, next;Edge() {}} static void addEdge(int u, int v, int w) {edges[++tot] = new Edge();edges[tot].to = v;edges[tot].w = w;edges[tot].next = head[u];head[u] = tot;}static void spfa(int S) {Arrays.fill(dist, INF);dist[S] = 0;Queue<Integer> q = new ArrayDeque<>();q.add(S);inq[S] = true;while (!q.isEmpty()) {int v = q.poll();inq[v] = false;for (int i = head[v]; i != 0; i = edges[i].next) {int to = edges[i].to, w = edges[i].w;if (dist[to] > dist[v] + w) {dist[to] = dist[v] + w;if (!inq[to]) {q.add(to);inq[to] = true;}}}}}public static void main(String[] args) throws IOException {  Scanner sc = new Scanner(new BufferedInputStream(System.in));BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));while (sc.hasNext()) {int E = sc.nextInt();   //Tint V = sc.nextInt();   //Sint D = sc.nextInt();   //Ddist = new int[MAXN];edges = new Edge[2*E+50];inq = new boolean[MAXN];head = new int[MAXN];for (int i = 0; i < E; i++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();addEdge(a, b, c);addEdge(b, a, c);}for (int i = 0; i < V; i++) {int adj = sc.nextInt();addEdge(1, adj, 0);addEdge(adj, 1 , 0);}spfa(1);int min = INF;for (int i = 0; i < D; i++) {int want = sc.nextInt();if (dist[want] < min)min = dist[want];}System.out.println(min);tot = 0;}}
}

复杂度分析

• 时间复杂度： O ( k E ) O(kE) O(kE)，
• 空间复杂度： O ( . . . ) O(...) O(...)，

方法二：多源最短路

• 可以借鉴多源 bfs 的思想，预先将多个临近城市加到 queue 中，然后一起跑最短路。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{static int V, E, D;static Edge[] edges;static int[] dist, head;static boolean[] vis, inq;static int[] adj;static int tot;static int INF = 0x3f3f3f3f;static int MAXN = 1000 + 50; static class Edge {int to, w, next;Edge() {}} static void addEdge(int u, int v, int w) {edges[++tot] = new Edge();edges[tot].to = v;edges[tot].w = w;edges[tot].next = head[u];head[u] = tot;}static void spfa() {Arrays.fill(dist, INF);Queue<Integer> q = new ArrayDeque<>();for (int a : adj) {q.add(a);inq[a] = true;dist[a] = 0;}while (!q.isEmpty()) {int v = q.poll();inq[v] = false;for (int i = head[v]; i != 0; i = edges[i].next) {int to = edges[i].to, w = edges[i].w;if (dist[to] > dist[v] + w) {dist[to] = dist[v] + w;if (!inq[to]) {q.add(to);inq[to] = true;}}}}}public static void main(String[] args) throws IOException {  Scanner sc = new Scanner(new BufferedInputStream(System.in));BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));while (sc.hasNext()) {int E = sc.nextInt();   //Tint V = sc.nextInt();   //Sint D = sc.nextInt();   //Ddist = new int[MAXN];edges = new Edge[2*E+50];inq = new boolean[MAXN];head = new int[MAXN];for (int i = 0; i < E; i++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();addEdge(a, b, c);addEdge(b, a, c);}adj = new int[V];for (int i = 0; i < V; i++) {adj[i] = sc.nextInt();}spfa();int min = INF;for (int i = 0; i < D; i++) {int want = sc.nextInt();min = Math.min(min, dist[want]);}System.out.println(min);tot = 0;}}
}

复杂度分析

• 时间复杂度： O ( k E ) O(kE) O(kE)，
• 空间复杂度： O ( . . . ) O(...) O(...)，

方法三：临界矩阵

这里讲几个点把，用矩阵存储图，记得去重边（即，取最小边）

其他参考文章：这里

【图论】C

一、题目描述

虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗。

但是草儿仍然很喜欢旅行，因为在旅途中会遇见很多人（白马王子，⁰），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……

眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input

• 输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
• 接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
• 接着的第T+1行有S个数，表示和草儿家相连的城市；
• 接着的第T+2行有D个数，表示草儿想去地方。

Output

• 输出草儿能去某个喜欢的城市的最短时间。

Input  
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
Sample Output
9

二、题解

方法一：多源转单源

• 因为草儿只能从与家相邻的城市出发，而去这些相邻城市是不花费前时间的，所以这些城市可以看成图中与起点相连而且边权为 0 的结点。
• 然后，就是跑最短路算法就行了。

重大发现：tot 是静态变量，如果在有多组数据测试的时候，一定要在没一组数据测试完毕之后将 tot 清零。

未知错误：总是得到一个 WA…

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{static int V, E, D;static Edge[] edges;static int[] dist, head;static boolean[] vis, inq;static int[] want;static int tot;static int INF = 0x3f3f3f3f;static int MAXN = 1000 + 50; static class Edge {int to, w, next;Edge() {}} static void addEdge(int u, int v, int w) {edges[++tot] = new Edge();edges[tot].to = v;edges[tot].w = w;edges[tot].next = head[u];head[u] = tot;}static void spfa(int S) {Arrays.fill(dist, INF);dist[S] = 0;Queue<Integer> q = new ArrayDeque<>();q.add(S);inq[S] = true;while (!q.isEmpty()) {int v = q.poll();inq[v] = false;for (int i = head[v]; i != 0; i = edges[i].next) {int to = edges[i].to, w = edges[i].w;if (dist[to] > dist[v] + w) {dist[to] = dist[v] + w;if (!inq[to]) {q.add(to);inq[to] = true;}}}}}public static void main(String[] args) throws IOException {  Scanner sc = new Scanner(new BufferedInputStream(System.in));BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));while (sc.hasNext()) {int E = sc.nextInt();   //Tint V = sc.nextInt();   //Sint D = sc.nextInt();   //Ddist = new int[MAXN];edges = new Edge[2*E+50];inq = new boolean[MAXN];head = new int[MAXN];for (int i = 0; i < E; i++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();addEdge(a, b, c);addEdge(b, a, c);}for (int i = 0; i < V; i++) {int adj = sc.nextInt();addEdge(1, adj, 0);addEdge(adj, 1 , 0);}spfa(1);int min = INF;for (int i = 0; i < D; i++) {int want = sc.nextInt();if (dist[want] < min)min = dist[want];}System.out.println(min);tot = 0;}}
}

复杂度分析

• 时间复杂度： O ( k E ) O(kE) O(kE)，
• 空间复杂度： O ( . . . ) O(...) O(...)，

方法二：多源最短路

• 可以借鉴多源 bfs 的思想，预先将多个临近城市加到 queue 中，然后一起跑最短路。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{static int V, E, D;static Edge[] edges;static int[] dist, head;static boolean[] vis, inq;static int[] adj;static int tot;static int INF = 0x3f3f3f3f;static int MAXN = 1000 + 50; static class Edge {int to, w, next;Edge() {}} static void addEdge(int u, int v, int w) {edges[++tot] = new Edge();edges[tot].to = v;edges[tot].w = w;edges[tot].next = head[u];head[u] = tot;}static void spfa() {Arrays.fill(dist, INF);Queue<Integer> q = new ArrayDeque<>();for (int a : adj) {q.add(a);inq[a] = true;dist[a] = 0;}while (!q.isEmpty()) {int v = q.poll();inq[v] = false;for (int i = head[v]; i != 0; i = edges[i].next) {int to = edges[i].to, w = edges[i].w;if (dist[to] > dist[v] + w) {dist[to] = dist[v] + w;if (!inq[to]) {q.add(to);inq[to] = true;}}}}}public static void main(String[] args) throws IOException {  Scanner sc = new Scanner(new BufferedInputStream(System.in));BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));while (sc.hasNext()) {int E = sc.nextInt();   //Tint V = sc.nextInt();   //Sint D = sc.nextInt();   //Ddist = new int[MAXN];edges = new Edge[2*E+50];inq = new boolean[MAXN];head = new int[MAXN];for (int i = 0; i < E; i++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();addEdge(a, b, c);addEdge(b, a, c);}adj = new int[V];for (int i = 0; i < V; i++) {adj[i] = sc.nextInt();}spfa();int min = INF;for (int i = 0; i < D; i++) {int want = sc.nextInt();min = Math.min(min, dist[want]);}System.out.println(min);tot = 0;}}
}

复杂度分析

• 时间复杂度： O ( k E ) O(kE) O(kE)，
• 空间复杂度： O ( . . . ) O(...) O(...)，

方法三：临界矩阵

这里讲几个点把，用矩阵存储图，记得去重边（即，取最小边）

其他参考文章：这里