图论:常见的最短路算法模板
Resolmi Newbie

849. Dijkstra 求最短路 I

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出-1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出-1。

数据范围, 图中涉及边长均不超过 10000。

进阶, 图中涉及边长均不超过 10000。

输入样例:

3 3
1 2 2
2 3 1
1 3 4

输出样例:

3

解法一

Dijkstra 适用于非负权图,其核心思路就是将所有的点划分为两部分,一部分是已经确定最短路的点集合,这个集合最开始只有源点。另一部分是未确定最短路的点集合

  1. 首先将刚加入的点的所有出边进行松弛(最开始就只有源点
  2. 然后在中找一个离源点最近的,那么这个点的最短路就确定了,因为这个点当前的最短路必然是经过集合中的点进行松弛过后的,且图没有负权,所以这个点不可能再通过其他未确定的点中转来缩短距离(如果有负权就可能,所以 Dijkstra 无法处理存在负权的图),将其标记进入集合,然后重复步骤一,直到所有点都加入集合

Dijkstra 暴力写法,这题题目数据范围比较小,所以直接建邻接矩阵然后跑 Dijkstra,时间复杂度

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int INF = 0x3f3f3f3f;
int[] in = read(br);
int N = in[0], M = in[1];
//邻接矩阵
int[][] w = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(w[i], INF);
}
for (int i = 0; i < M; i++) {
int[] t = read(br); //t[0]->t[1]
int x = t[0]-1, y = t[1]-1;
w[x][y] = Math.min(t[2], w[x][y]);
}
//dis[i]: 源点 s 到 i 的最短距离
int[] dis = new int[N];
boolean[] vis = new boolean[N];
Arrays.fill(dis, INF);
dis[0] = 0;
for (int i = 0; i < N; i++) {
int min = -1;
//未确定最短路的点中距离 s 最近的点
for (int j = 0; j < N; j++) {
if (!vis[j] && (min==-1 || dis[j] < dis[min])) {
min = j;
}
}
//松弛
vis[min] = true;
for (int j = 0; j < N; j++) {
if (!vis[j]) {
dis[j] = Math.min(dis[j], dis[min] + w[min][j]);
}
}
}
out.println(dis[N-1] == INF ? -1 : dis[N-1]);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

解法二

堆优化的 Dijkstra,上面的解法在数据量大的时候显然是不适用的,首先我们不能再使用邻接矩阵了,需要改用邻接表,同时采用小根堆来快速的获取未确定点集中距离源点最近的点,堆中需要存储节点编号以及当前节点最短路,时间复杂度大概,但是最坏情况下边数可能会达到级别(稠密图),导致堆优化的复杂度反而低于朴素的,但是大多数情况下边数不会有这么多,除此之外还有一些其它的优化方法,详见 OI-Wiki

import java.util.*;
import java.io.*;

class Main {

static class Node {
int idx, val;
public Node(int idx, int val) {
this.idx = idx;
this.val = val;
}
}

static int idx;
static int N, M;
static int[] h, e, ne, w;
//a->b
static void add(int a, int b, int c) {
w[idx] = c; e[idx] = b;
ne[idx] = h[a]; h[a] = idx++;
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int INF = 0x3f3f3f3f;
int[] in = read(br);
N = in[0]; M = in[1];
h = new int[N+1]; e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
Arrays.fill(h, -1);
for (int i = 0; i < M; i++) {
int[] t = read(br);
add(t[0], t[1], t[2]);
}
PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2)->n1.val-n2.val);
int[] dis = new int[N+1];
//记录已经确定最短路的点集 s
boolean[] vis = new boolean[N+1];
Arrays.fill(dis, INF);
dis[1] = 0;
pq.add(new Node(1, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
//从未确定最短路的点中找 dis 最小的(如果弹出来的是已经确定过的就会跳过)
int i = node.idx, v = node.val;
if (vis[i]) continue;
//标记该点已经确定最短路
vis[i] = true;
//松弛该点出边
for (int j = h[i]; j != -1; j = ne[j]) {
if (v+w[j] < dis[e[j]]) {
dis[e[j]] = v+w[j];
pq.add(new Node(e[j], v+w[j]));
}
}
}
out.println(dis[N] == INF ? -1 : dis[N]);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

Java 其实还有一种更加简洁的写法,利用闭包,不用新建 Node 类

import java.util.*;
import java.io.*;

class Main {

static int idx;
static int N, M;
static int[] h, e, ne, w;
//a->b
static void add(int a, int b, int c) {
w[idx] = c; e[idx] = b;
ne[idx] = h[a]; h[a] = idx++;
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int INF = 0x3f3f3f3f;
int[] in = read(br);
N = in[0]; M = in[1];
h = new int[N]; e = new int[M]; ne = new int[M]; w = new int[M];
Arrays.fill(h, -1);
for (int i = 0; i < M; i++) {
int[] t = read(br);
add(t[0]-1, t[1]-1, t[2]);
}
int[] dis = new int[N];
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->dis[a]-dis[b]);
//记录已经确定最短路的点集 s
boolean[] vis = new boolean[N];
Arrays.fill(dis, INF);
dis[0] = 0;
pq.add(0);
while (!pq.isEmpty()) {
int i = pq.poll();
if (vis[i]) continue;
//标记该点已经确定最短路
vis[i] = true;
//松弛该点能到达的点的 dis
for (int j = h[i]; j != -1; j = ne[j]) {
if (dis[i]+w[j] < dis[e[j]]) {
dis[e[j]] = dis[i]+w[j];
pq.add(e[j]);
}
}
}
out.println(dis[N-1] == INF ? -1 : dis[N-1]);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

853. 有边数限制的最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。

注意:图中可能存在负权回路

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径,则输出“impossible”。

数据范围,且任意边长的绝对值不超过

输入样例:

3 3 1
1 2 1
2 3 1
1 3 3

输出样例:

3

解法一

Bellman−Ford,负权最短路算法,可以处理负权边,同时可以检测负权回路(回路的总权值为负数)。算法基于动态规划设计,为源点经过最多条边到达节点的最短路。一共有个点,所以任意点的最短路最多经过的边数为(负环没有最短路)

  • 入口:
  • 转移:遍历所有的边,
  • 出口:
  • 时间复杂度:

本题中限制了边数,所以我们外层循环只到就行了,具体代码实现如下:

import java.util.*;
import java.io.*;

class Main {

static class Edge {
int s, e;
int v;
public Edge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
int INF = 0x3f3f3f3f;
int N = in[0], M = in[1], K = in[2];
Edge[] eds = new Edge[M];
for (int i = 0; i < M; i++) {
int[] t = read(br);
eds[i] = new Edge(t[0], t[1], t[2]);
}
int[][] dis = new int[K+1][N+1];
for (int i = 0; i <= K; i++) {
Arrays.fill(dis[i], INF);
dis[i][1] = 0;
}
for (int i = 1; i <= K; i++) {
for (int j = 0; j < M; j++) {
int s = eds[j].s, e = eds[j].e;
if (dis[i-1][s] == INF) continue;
// 不加 dis[i-1][e] 也能过 OJ,但是最好还是加上
// dis[i][e] = Math.min(dis[i][e], dis[i-1][s] + eds[j].v);
dis[i][e] = Math.min(dis[i-1][e], Math.min(dis[i][e], dis[i-1][s] + eds[j].v));
}
}
out.println(dis[K][N] == INF ? "impossible" : dis[K][N]);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

这里存个疑问,为什么这里转移方程不加也能 AC?这里加上一定不会错,但是不加会有点迷惑。

这里我的想法是,如果不加,状态的定义其实就变成了:恰好经过条边的时候的最短路,这样出口就是,但是由于我们在入口定义了,误打误撞的导致出口变成了,具体原因不想深究,明白错哪里就行了,总之这是一种不伦不类的写法,不要这样写,正确写法如下:

状态定义为恰好经过 i 条边的写法
import java.util.*;
import java.io.*;

class Main {

static class Edge {
int s, e;
int v;
public Edge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
int INF = 0x3f3f3f3f;
int N = in[0], M = in[1], K = in[2];
Edge[] eds = new Edge[M];
for (int i = 0; i < M; i++) {
int[] t = read(br);
eds[i] = new Edge(t[0], t[1], t[2]);
}
//恰好经过 i 条边
int[][] dis = new int[K+1][N+1];
for (int i = 0; i <= K; i++) {
Arrays.fill(dis[i], INF);
}
dis[0][1] = 0;
for (int i = 1; i <= K; i++) {
for (int j = 0; j < M; j++) {
int s = eds[j].s, e = eds[j].e;
if (dis[i-1][s] == INF) continue;
dis[i][e] = Math.min(dis[i][e], dis[i-1][s] + eds[j].v);
}
}
int res = INF;
for (int i = 0; i <= K; i++) {
res = Math.min(res, dis[i][N]);
}
out.println(res == INF ? "impossible" : res);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

解法二

实际中通常写的都是一维的 Bellman−Ford,降维后在中,不仅包含了前一轮最多经过条边到达的最短路,同时也包含了当前轮最多经过条边到达的最短路,所以最终经过次松弛得到的结果可能不只经过了条边,所以在这题中我们需要保存一下上一轮的状态,用上一轮的来更新当前轮的,保证最后结果经过的边不超过

import java.util.*;
import java.io.*;

class Main {

static class Edge {
int s, e;
int v;
public Edge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
int INF = 0x3f3f3f3f;
int N = in[0], M = in[1], K = in[2];
Edge[] eds = new Edge[M];
for (int i = 0; i < M; i++) {
int[] t = read(br);
eds[i] = new Edge(t[0]-1, t[1]-1, t[2]);
}
//dis[i][j]: 源点最多经过 i 条边,到达 j 点的最短路
int[] dis = new int[N];
//上一轮经过 (i-1) 次松弛后的结果,避免串联更新(当前轮更新当前轮),因为这题需要保证最多只能经过 K 条边
int[] last = new int[N];
Arrays.fill(dis, INF);
dis[0] = 0;
for (int i = 0; i < K; i++) {
System.arraycopy(dis, 0, last, 0, N);
for (int j = 0; j < M; j++) {
int s = eds[j].s, e = eds[j].e;
if (last[s] == INF) continue;
dis[e] = Math.min(dis[e], last[s] + eds[j].v);
}
}
out.println(dis[N-1] == INF ? "impossible" : dis[N-1]);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

如果数据量比较大可以改成 SPFA,如下:

import java.util.*;
import java.io.*;

class Main {

static int idx;
static int N, M, K;
static int[] h, e, ne, w;
//a->b
static void add(int a, int b, int c) {
w[idx] = c; e[idx] = b;
ne[idx] = h[a]; h[a] = idx++;
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] in = read(br);
int INF = 0x3f3f3f3f;
N = in[0]; M = in[1]; K = in[2];
e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
h = new int[N+1]; Arrays.fill(h, -1);
for (int i = 0; i < M; i++) {
int[] t = read(br);
add(t[0], t[1], t[2]);
}
//恰好经过 i 条边到达 j 的最短路
int[][] dis = new int[K+1][N+1];
boolean[][] vis = new boolean[K+1][N+1];
for (int i = 0; i <= K; i++) {
Arrays.fill(dis[i], INF);
}
dis[0][1] = 0; vis[0][1] = true;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{1, 0});
while (!queue.isEmpty()) {
int[] top = queue.poll();
int i = top[0], step = top[1];
if (step >= K) continue;
vis[step][i] = false;
for (int j = h[i]; j != -1; j = ne[j]) {
int k = e[j];
if (w[j]==INF || dis[step][i]==INF) continue;
if (dis[step+1][k] > dis[step][i] + w[j]) {
dis[step+1][k] = dis[step][i] + w[j];
if (!vis[step+1][k]) {
queue.add(new int[]{k, step+1});
vis[step+1][k] = true;
}
}
}
}
int res = INF;
for (int i = 0; i <= K; i++) {
res = Math.min(res, dis[i][N]);
}
out.println(res==INF ? "impossible" : res);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

851. spfa 求最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible。数据保证不存在负权回路

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出”impossible”。

数据范围,图中涉及边长绝对值均不超过 10000。

输入样例:

3 3
1 2 5
2 3 -3
1 3 4

输出样例:

2

解法一

SPFA 基于 Bellman−Ford 进行优化,最坏时间复杂度依然是,但是常规情况下速度还是很快的,时间复杂度不稳定。

优化的点在于 BF 在松弛过程中有一些顶点可能早已经得到了最短路,后续不会再被松弛,但是依然会进行判断,浪费了时间,所以我们可以考虑只对最短路估计值减小了的顶点的出边进行松弛

具体实现中,我们可以采用一个 FIFO 队列存储松弛成功的顶点,最开始就只有源点,入队的顶点需要进行标记,对队列中顶点的出边进行松弛,将松弛成功并且没有标记的顶点继续加入队列。乍一看和 BFS 类似,但是这里其实有一个很大的区别:SPFA 在队首元素出队后需要将其标记取消,因为队首顶点后续可能还会被其他顶点松弛,这也是 SPFA 时间复杂度不稳定的原因(容易被卡,但是最差也是退化到)。

import java.util.*;
import java.io.*;

class Main {

static int idx;
static int[] e, h, ne, w;
//a->b
public static void add(int a, int b, int c){
e[idx] = b; w[idx] = c;
ne[idx] = h[a]; h[a] = idx++;
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int INF = 0x3f3f3f3f;
int[] in = read(br);
int N = in[0], M = in[1];
e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
h = new int[N+1]; Arrays.fill(h, -1);
for (int i = 0; i < M; i++) {
int[] t = read(br);
add(t[0], t[1], t[2]);
}
Queue<Integer> queue = new LinkedList<>();
boolean[] vis = new boolean[N+1];
int[] dis = new int[N+1];
Arrays.fill(dis, INF);
dis[1] = 0; vis[1] = true;
queue.add(1);
while (!queue.isEmpty()) {
int top = queue.poll();
vis[top] = false;
for (int i = h[top]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[top] + w[i]) {
dis[j] = dis[top] + w[i];
if (!vis[j]) {
queue.add(j);
vis[j] = true;
}
}
}
}
out.println(dis[N] == INF ? "impossible" : dis[N]);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

852. spfa 判断负环

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

如果图中存在负权回路,则输出“Yes”,否则输出“No”。

数据范围,图中涉及边长绝对值均不超过 10000。

输入样例:

3 3
1 2 -1
2 3 4
3 1 -4

输出样例:

Yes

解法一

题目是判断图有没有负环,但是图不一定是联通的,单纯从某个点出发并不一定能走到负环上,暴力的方法就是对每个点作为源点做一次 spfa,但是这样显然复杂度过高

考虑增加一个虚拟节点,和所有的点增加一条权值为 0 的单向边,新增加的虚拟节点一定能走到负环上,所以我们对虚拟节点做一次 spfa 就能判断出原图是否有负环
mark
模拟第一次入队出队,虚拟节点出队后就会将所有的节点入队,为虚拟源点到当前节点的最短路,所以一开始所有的,不用初始化为

然后就是关键的判环步骤,我们只需要记录下每个点到虚拟源点的边的数量就行了(初始),如果有负环就会无限制的松弛负环上的边,在负环路上打转,所以如果松弛后某个点到虚拟源点的边的数量大于等于就说明存在负环

import java.util.*;
import java.io.*;

class Main {

static int INF = 0x3f3f3f3f;
static int N, M;
static int idx;
static int[] e, h, ne, w;
//a->b
public static void add(int a, int b, int c){
e[idx] = b; w[idx] = c;
ne[idx] = h[a]; h[a] = idx++;
}

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
N = in[0]; M = in[1];
e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
h = new int[N+1]; Arrays.fill(h, -1);
for (int i = 0; i < M; i++) {
int[] t = read(br);
add(t[0], t[1], t[2]);
}
out.println(spfa() ? "Yes" : "No");
out.flush();
}

public static boolean spfa() {
Queue<Integer> queue = new LinkedList<>();
int[] dis = new int[N+1];
boolean[] vis = new boolean[N+1];
int[] cnt = new int[N+1];
for (int i = 1; i <= N; i++) {
queue.add(i);
vis[i] = true;
cnt[i] = 1;
}
while (!queue.isEmpty()) {
int top = queue.poll();
vis[top] = false;
for (int i = h[top]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[top] + w[i]) {
dis[j] = dis[top] + w[i];
cnt[j] = cnt[top] + 1;
if (cnt[j] >= N+1) return true;
if (!vis[j]) {
queue.add(j);
vis[j] = true;
}
}
}
}
return false;
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

854. Floyd 求最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出“impossible”。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 n,m,k

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

接下来 k 行,每行包含两个整数 x,y,表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出“impossible”。

数据范围, 图中涉及边长绝对值均不超过 10000。

输入样例:

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例:

impossible
1

解法一

Floyd 是一个多源的最短路算法,也就是可以同时求出图中任意两点之间的最短路,本质是一个 DP,时间复杂度较高

  • 状态定义:,从经过前个点中转后的最短路
  • 入口:
  • 转移:
  • 出口:,时间复杂度

由于仅仅依赖,所以通常我们这里都会降维写二维的

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
int N = in[0], M = in[1], K = in[2];
int INF = 0x3f3f3f3f;
int[][] dis = new int[N+1][N+1];
for (int i = 1; i <= N; i++) {
Arrays.fill(dis[i], INF);
dis[i][i] = 0;
}
for (int i = 0; i < M; i++) {
int[] t = read(br);
int x = t[0], y = t[1];
dis[x][y] = Math.min(dis[x][y], t[2]);
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dis[i][k] == INF || dis[k][j] == INF) continue;
dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
for (int i = 0; i < K; i++) {
int[] q = read(br);
int res = dis[q[0]][q[1]];
out.println(res == INF ? "impossible" : res);
}
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

三维的写法:854. Floyd 求最短路 三维 DP 写法,不降维

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
int N = in[0], M = in[1], K = in[2];
int INF = 0x3f3f3f3f;
int[][][] dis = new int[N+1][N+1][N+1];
for (int i = 1; i <= N; i++) {
Arrays.fill(dis[0][i], INF);
dis[0][i][i] = 0;
}
for (int i = 0; i < M; i++) {
int[] t = read(br);
int x = t[0], y = t[1];
dis[0][x][y] = Math.min(dis[0][x][y], t[2]);
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dis[k-1][i][k] == INF || dis[k-1][k][j] == INF) {
dis[k][i][j] = dis[k-1][i][j];
} else {
dis[k][i][j] = Math.min(dis[k-1][i][j], dis[k-1][i][k] + dis[k-1][k][j]);
}
}
}
}
for (int i = 0; i < K; i++) {
int[] q = read(br);
int res = dis[N][q[0]][q[1]];
out.println(res == INF ? "impossible" : res);
}
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
  • 本文标题:图论:常见的最短路算法模板
  • 本文作者:Resolmi
  • 创建时间:2021-03-17 00:00:00
  • 本文链接:https://imlgw.top/2021/03/17/c163e5c9/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论