ZT41 【模板】单源最短路Ⅰ ‖ 无权图
描述
对于给定的由 𝑛n 个顶点、𝑚m 条边构成的有向无权图（不一定连通）。依次输出以顶点 𝑠s 为起点、到全部顶点的最短路径长度。
输入描述：
第一行输入三个整数 𝑛,𝑚,𝑠(1≦𝑛,𝑚≦2×106; 1≦𝑠≦𝑛)n,m,s(1≦n,m≦2×106; 1≦s≦n) 代表顶点数量、边数量、起点编号。
此后 𝑚m 行，第 𝑖i 行输入两个整数 𝑢𝑖ui 和 𝑣𝑖(1≦𝑢𝑖,𝑣𝑖≦𝑛; 𝑢𝑖≠𝑣𝑖)vi(1≦ui,vi≦n; ui=vi) 表示图上第 𝑖i 条边单向连接顶点 𝑢𝑖ui 和 𝑣𝑖vi 。
图可能不连通、可能存在重边。不存在自环。输出描述：
在一行上输出 𝑛n 个整数，依次代表到各个顶点的最短路径。特别的，若不存在路径，则输出 −1−1 。
示例1
输入：
4 7 2 1 3 1 4 2 1 4 1 2 4 4 3 4 3复制输出：
1 0 2 1复制说明：
示例2
输入：
3 2 1 1 2 2 1复制输出：
0 1 -1复制说明：
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
String[] firstLine = reader.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
int m = Integer.parseInt(firstLine[1]);
int s = Integer.parseInt(firstLine[2]);
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
String[] edge = reader.readLine().split(" ");
int u = Integer.parseInt(edge[0]);
int v = Integer.parseInt(edge[1]);
graph.get(u).add(v);
}
int[] dist = bfsShortestPath(n, s, graph);
for (int i = 1; i <= n; i++) {
writer.print(dist[i] + " ");
}
reader.close();
writer.close();
}
public static int[] bfsShortestPath(int n, int s, List<List<Integer>> graph) {
int[] dist = new int[n + 1];
Arrays.fill(dist, -1);
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
dist[s] = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph.get(u)) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
queue.add(v);
}
}
}
return dist;
}
}ZT42 【模板】单源最短路Ⅲ ‖ 非负权图
描述
对于给定的由 𝑛n 个顶点、𝑚m 条边构成的有向赋权图（不一定连通），权值仅为非负整数。依次输出以顶点 𝑠s 为起点、到全部顶点的最短路径长度。
提示
输入描述：
第一行输入三个整数 𝑛,𝑚,𝑠(1≦𝑛,𝑚≦5×105; 1≦𝑠≦𝑛)n,m,s(1≦n,m≦5×105; 1≦s≦n) 代表顶点数量、边数量、起点编号。
此后 𝑚m 行，第 𝑖i 行输入三个整数 𝑢𝑖,𝑣𝑖ui,vi 和 𝑤𝑖(1≦𝑢𝑖,𝑣𝑖≦𝑛; 𝑢𝑖≠𝑣𝑖; 0≦𝑤𝑖≦109)wi(1≦ui,vi≦n; ui=vi; 0≦wi≦109) 表示图上第 𝑖i 条边单向连接顶点 𝑢𝑖ui 和 𝑣𝑖vi 、边权为 𝑤𝑖wi 。
图可能不连通、可能存在重边。不存在自环。输出描述：
在一行上输出 𝑛n 个整数，依次代表到各个顶点的最短路径。特别的，若终点为自己，输出 00 ，若不存在路径，则输出 −1−1 。
示例1
输入：
4 7 2 1 3 1 1 4 0 2 1 1 4 1 0 2 4 5 4 3 1 4 3 5复制输出：
1 0 2 1复制说明：
示例2
输入：
3 2 1 1 2 1 2 1 3复制输出：
0 1 -1复制说明：
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
String[] firstLine = reader.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
int m = Integer.parseInt(firstLine[1]);
int s = Integer.parseInt(firstLine[2]);
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
String[] edge = reader.readLine().split(" ");
int u = Integer.parseInt(edge[0]);
int v = Integer.parseInt(edge[1]);
int w = Integer.parseInt(edge[2]);
graph.get(u).add(new Edge(v, w));
}
long[] dist = dijkstra(n, s, graph);
for (int i = 1; i <= n; i++) {
writer.print(dist[i] + " ");
}
reader.close();
writer.close();
}
public static long[] dijkstra(int n, int s, List<List<Edge>> graph) {
long[] dist = new long[n + 1];
Arrays.fill(dist, Long.MAX_VALUE);
dist[s] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(
node -> node.dist));
pq.add(new Node(s, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.vertex;
long d = node.dist;
if (d > dist[u]) continue;
for (Edge edge : graph.get(u)) {
int v = edge.to;
long w = edge.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.add(new Node(v, dist[v]));
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] == Long.MAX_VALUE) {
dist[i] = -1;
}
}
return dist;
}
static class Edge {
int to;
long weight;
Edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
}
static class Node {
int vertex;
long dist;
Node(int vertex, long dist) {
this.vertex = vertex;
this.dist = dist;
}
}
}ZT43 【模板】最小生成树
描述
对于给定的由 𝑛n 个顶点、𝑚m 条边构成的无向赋权连通图，权值为整数。求解这张图的最小生成树。
输入描述：
第一行输入两个整数 𝑛,𝑚(1≦𝑛≦5×105; 𝑛−1≦𝑚≦5×105)n,m(1≦n≦5×105; n−1≦m≦5×105) 代表顶点数量、边数量。
此后 𝑚m 行，第 𝑖i 行输入三个整数 𝑢𝑖,𝑣𝑖ui,vi 和 𝑤𝑖(1≦𝑢𝑖,𝑣𝑖≦𝑛; 𝑢𝑖≠𝑣𝑖; −109≦𝑤𝑖≦109)wi(1≦ui,vi≦n; ui=vi; −109≦wi≦109) 表示图上第 𝑖i 条边双向连接顶点 𝑢𝑖ui 和 𝑣𝑖vi 、边权为 𝑤𝑖wi 。
图可能存在重边。保证连通、不存在自环。输出描述：
在第一行上输出一个整数代表最小生成树的树边权重之和。
在第二行上输出 𝑛−1n−1 个不同的整数，代表你所找到的最小生成树的边的编号。编号即输入顺序，从 11 开始计数。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。示例1
输入：
5 7 4 5 2 1 3 0 1 4 1 2 1 1 4 1 0 2 4 0 4 3 0复制输出：
2 2 6 5 1
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int[] fa;
static List<Integer> res;
static Edge[] g;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
String[] firstLine = reader.readLine().split(" ");
n = Integer.parseInt(firstLine[0]);
m = Integer.parseInt(firstLine[1]);
fa = new int[n + 1];
res = new ArrayList<>();
g = new Edge[m + 1];
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i <= m; i++) {
String[] edge = reader.readLine().split(" ");
int u = Integer.parseInt(edge[0]);
int v = Integer.parseInt(edge[1]);
long w = Long.parseLong(edge[2]);
g[i] = new Edge(u, v, w, i);
}
Arrays.sort(g, 1, m + 1);
Kruskal();
writer.println(totalWeight);
for (int edgeIndex : res) {
writer.print(edgeIndex + " ");
}
reader.close();
writer.close();
}
static long totalWeight = 0;
static void Kruskal() {
int cont = 0;
for (int i = 1; i <= m; i++) {
Edge edge = g[i];
int u = edge.u;
int v = edge.v;
long w = edge.w;
int id = edge.id;
if (find(u) == find(v)) continue;
res.add(id);
totalWeight += w;
cont++;
union(u, v);
if (cont == n - 1) {
return;
}
}
}
static int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
static void union(int x, int y) {
fa[find(x)] = find(y);
}
static class Edge implements Comparable<Edge> {
int u, v;
long w;
int id;
Edge(int u, int v, long w, int id) {
this.u = u;
this.v = v;
this.w = w;
this.id = id;
}
@Override
public int compareTo(Edge other) {
return Long.compare(this.w, other.w);
}
}
}