图论：单源最短路的综合应用
1135. 新年好
重庆城里有 $n$ 个车站， $m$ 条 双向 公路连接其中的某些车站。
每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。
在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 $1$ ，他有五个亲戚，分别住在车站 $a,b,c,d,e$ 。
过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。
怎样走，才需要最少的时间？
输入格式
第一行：包含两个整数 $n,m$ 分别表示车站数目和公路数目。
第二行：包含五个整数 $a,b,c,d,e$ 分别表示五个亲戚所在车站编号。
以下 $m$ 行，每行三个整数 $x,y,t$ 表示公路连接的两个车站编号和时间。
输出格式
输出仅一行，包含一个整数 $T$ ，表示最少的总时间。
数据范围
- $1≤n≤50000$
- $1≤m≤10^5$
- $1<a,b,c,d,e≤n$
- $1≤x,y≤n$
- $1≤t≤100$
输入样例：
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
输出样例：
21
解法一
SPFA 会被卡，直接写的堆优化 Dijkstra，写的比较丑。
首先预处理出关键点之间的最短路，然后直接 dfs 全排列求最小值就行了
import java.io.*;
import java.util.*;
class Main {
static int idx;
static int[] e, ne, h, w;
static int N, M;
static int[] tar;
static int INF = 0x3f3f3f3f;
static boolean[] vis;
static HashMap<String, Integer> dp = new HashMap<>();
//a->b
public static void add(int a, int b, int c){
e[idx] = b; ne[idx] = h[a];
w[idx] = c; h[a] = idx++;
}
public static void main(String... args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
int[] in = read(br);
N = in[0]; M = in[1];
h = new int[N+1]; e = new int[2*M+1]; ne = new int[2*M+1]; w = new int[2*M+1];
Arrays.fill(h, -1);
tar = read(br);
for (int i = 0; i < M; i++) {
int[] _in = read(br);
add(_in[0], _in[1], _in[2]);
add(_in[1], _in[0], _in[2]);
}
// 初始化以各个点为源点的最短路
dijkstra(1);
for (int i = 0; i < tar.length; i++) {
dijkstra(tar[i]);
}
vis = new boolean[tar.length];
int res = INF;
for (int i = 0; i < tar.length; i++) {
vis[i] = true;
res = Math.min(res, dp.get(1 + "," + tar[i]) + dfs(i));
vis[i] = false;
}
out.println(res);
out.flush();
}
public static int dfs(int c) {
boolean flag = false;
int res = INF;
for (int i = 0; i < tar.length; i++) {
if (vis[i]) continue;
vis[i] = true;
res = Math.min(res, dp.get(tar[c] + "," + tar[i]) + dfs(i));
vis[i] = false;
flag = true;
}
if (!flag) {
return 0;
}
return res;
}
public static void dijkstra(int s) {
int[] dis = new int[N+1];
Arrays.fill(dis, INF);
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dis[a] - dis[b]);
dis[s] = 0; pq.add(s);
boolean[] vis = new boolean[N+1];
while (!pq.isEmpty()) {
int i = pq.poll();
if (vis[i]) continue;
vis[i] = true;
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]);
}
}
}
for (int i = 0; i < tar.length; i++) {
dp.put(s + "," + tar[i], dis[tar[i]]);
}
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
public class AcWing1135_新年好 {
public static void main(String[] args) throws Exception{
new Main().main();
}
}
341. 最优贸易
$C$ 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。
任意两个城市之间最多只有一条道路直接相连。
这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。
$C$ 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。
设 C 国 n 个城市的标号从 $1∼n$ ，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。
在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。
阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。
因为阿龙主要是来 $C$ 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
现在给出 $n$ 个城市的水晶球价格， $m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。
请你告诉阿龙，他最多能赚取多少旅费。
注意：本题数据有加强。
输入格式
第一行包含 $2$ 个正整数 $n$ 和 $m$ ，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个城市的商品价格。
接下来 $m$ 行，每行有 3 个正整数， $x，y，z$ ，每两个整数之间用一个空格隔开。
如果 $z=1$ ，表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路；如果 $z=2$ ，表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。
输出格式
一个整数，表示答案。
数据范围
- $1≤n≤100000$
- $1≤m≤500000$
- $1≤各城市水晶球价格≤100$
输入样例：
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
输出样例：
5
解法一
这题目意思简化就是在一个非 DAG 的图上，求从一个点到另一个点的最大的点权值差。
和 abc188 的 E 题 Peddler 还挺像的，可以对比来看。
这个问题和最短路问题关联不大，主要是借助了 SPFA 的优化，实际上还是 Bellman-Ford 的 dp 思想。
理解了 Bellman-Ford，再来理解这题就很容易了，其实就是把 bf 的状态定义 $dp[i][j]$ 改成了从起点经过 $i$ 条边，到达 $j$ 点的最小点权值。显然这里也是符合 bf 的要求的，任意两点之间的最小点权值最多也只需要经过 $N-1$ 条边就能知道，所以也可以直接按照 bf 的思路去做，进行 $N-1$ 次迭代，遍历所有边，求最小点权值。
既然适用与 Bellman-Ford 那么我们就可以直接使用 SPFA 来做了。设置 $pMin[i]$ 为从 $1～i$ 过程中最低的价格， $pMax[i]$ 为从 $i～n$ 过程中最高的价格，最大收益为： $\max_1^n(pMax[i]-pMin[i])$ （注意求 $pMax$ 需要建反向边，方便计算）
import java.util.*;
import java.io.*;
class Main {
static int INF = 0x3f3f3f3f;
static int [] price;
static int N, M;
static int idx;
static int[] e, ne, h1, h2;
public static void add(int[] h, int a, int b) {
e[idx] = b; ne[idx] = h[a];
h[a] = idx++;
}
public static void main(String... args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] in = read(br);
N = in[0]; M = in[1];
h1 = new int[N+1]; h2 = new int[N+1];
Arrays.fill(h1, -1); Arrays.fill(h2, -1);
e = new int[(M+1)*4]; ne = new int[(M+1)*4];
int[] pMax = new int[N+1];
int[] pMin = new int[N+1];
//i-1
price = read(br);
for (int i = 0; i < M; i++) {
int[] t = read(br);
int a = t[0], b = t[1];
add(h1, a, b); add(h2, b, a);
if (t[2] == 2) {
add(h1, b, a); add(h2, a, b);
}
}
spfa(h1, pMin, 1);
spfa(h2, pMax, N);
int res = 0;
for (int i = 1; i <= N; i++) {
res = Math.max(res, pMax[i] - pMin[i]);
}
System.out.println(res);
}
public static void spfa(int[] h, int[] dp, int s) {
boolean[] vis = new boolean[N+1];
boolean flag = s == 1;
Arrays.fill(dp, flag ? INF : -INF);
Queue<Integer> que = new LinkedList<>();
que.add(s);
dp[s] = price[s-1];
vis[s] = true;
while (!que.isEmpty()) {
int i = que.poll();
vis[i] = false;
for (int j = h[i]; j != -1; j = ne[j]) {
int k = e[j];
if (flag) {
if (dp[k] > Math.min(dp[i], price[k-1])) {
dp[k] = Math.min(dp[i], price[k-1]);
if (!vis[k]) {
que.add(k);
vis[k] = true;
}
}
} else {
if (dp[k] < Math.max(dp[i], price[k-1])) {
dp[k] = Math.max(dp[i], price[k-1]);
if (!vis[k]) {
que.add(k);
vis[k] = true;
}
}
}
}
}
}
public static int[] read(BufferedReader reader) throws Exception {
return Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
public class AcWing341_最优贸易 {
public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("./input.txt"));
new Main().main();
}
}
这题其实用 SPFA 还是不太好（SPFA 已死），看见评论区还有好几种解法，分层图，缩点什么的，有时间再来看看。
1137. 选择最佳线路
有一天，琪琪想乘坐公交车去拜访她的一位朋友。 由于琪琪非常容易晕车，所以她想尽快到达朋友家。 现在给定你一张城市交通路线图，上面包含城市的公交站台以及公交线路的具体分布。
已知城市中共包含 $n$ 个车站（编号 $1 \sim n$ ）以及 $m$ 条公交线路。
每条公交线路都是 单向的，从一个车站出发直接到达另一个车站，两个车站之间可能存在多条公交线路。
琪琪的朋友住在 $s$ 号车站附近。
琪琪可以在任何车站选择换乘其它公共汽车。
请找出琪琪到达她的朋友家（附近的公交车站）需要花费的最少时间。
输入格式
输入包含多组测试数据。
每组测试数据第一行包含三个整数 $n,m,s$ ，分别表示车站数量，公交线路数量以及朋友家附近车站的编号。
接下来 $m$ 行，每行包含三个整数 $p,q,t$ ，表示存在一条线路从车站 $p$ 到达车站 $q$ ，用时为 $t$ 。
接下来一行，包含一个整数 $w$ ，表示琪琪家附近共有 $w$ 个车站，她可以在这 $w$ 个车站中选择一个车站作为始发站。
再一行，包含 $w$ 个整数，表示琪琪家附近的 $w$ 个车站的编号。
输出格式
每个测试数据输出一个整数作为结果，表示所需花费的最少时间。
如果无法达到朋友家的车站，则输出 -1。
每个结果占一行。
数据范围
- $n≤1000,m≤20000$
- $1≤s≤n$
- $0<w<n$
- $0<t≤1000$
输入样例：
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
输出样例：
1
-1
解法一
多个起点，任意终点
两种做法：
- 建立虚拟源点，连接所有起点，权值为 0，然后求从源点到终点的最短距离
- 建反向边，求终点到任意点的最短路，最后取到起点的最小值
这里使用第二种方法
package main
import (
"bufio"
"container/heap"
"fmt"
"os"
"strconv"
"strings"
)
var INF = int(0x3f3f3f3f)
var h []int
var e []int
var ne []int
var w []int
var idx int
func Add(a, b, c int) {
e[idx] = b
w[idx] = c
ne[idx] = h[a]
h[a] = idx
idx++
}
func main() {
// f, _ := os.Open("./input.txt")
// reader := bufio.NewReader(f)
reader := bufio.NewReader(os.Stdin)
for {
t, err := ReadArray(reader)
if err != nil {
break
}
n, m, s := t[0], t[1], t[2]
idx = 0
h = make([]int, n+1)
for i := 0; i <= n; i++ {
h[i] = -1
}
e = make([]int, m+1)
w = make([]int, m+1)
ne = make([]int, m+1)
for i := 0; i < m; i++ {
_t, _ := ReadArray(reader)
// 建反向边
Add(_t[1], _t[0], _t[2])
}
ReadArray(reader)
a, _ := ReadArray(reader)
fmt.Println(Dijkstra(n, s, a))
}
}
func Dijkstra(n int, s int, a []int) int {
pq := make(NodeHeap, 0)
vis := make([]bool, n+1)
dis := make([]int, n+1)
for i := 0; i <= n; i++ {
dis[i] = INF
}
heap.Push(&pq, &Node{
idx: s,
val: 0,
})
dis[s] = 0
for len(pq) > 0 {
cur := heap.Pop(&pq).(*Node)
i, v := cur.idx, cur.val
if vis[i] {
continue
}
vis[i] = true
for j := h[i]; j != -1; j = ne[j] {
if w[j]+v < dis[e[j]] {
dis[e[j]] = w[j] + v
heap.Push(&pq, &Node{e[j], dis[e[j]]})
}
}
}
min := INF
for _, v := range a {
min = Min(min, dis[v])
}
if min == INF {
return -1
}
return min
}
func Min(a, b int) int {
if a < b {
return a
}
return b
}
type Node struct {
idx int
val int
}
type NodeHeap []*Node
func (h NodeHeap) Len() int { return len(h) }
// 小顶堆
func (h NodeHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h NodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x interface{}) {
// Push 和 Pop 使用 pointer receiver 作为参数，
// 因为它们不仅会对切片的内容进行调整，还会修改切片的长度。
*h = append(*h, x.(*Node))
}
func (h *NodeHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func ReadLine(reader *bufio.Reader) (string, error) {
line, err := reader.ReadString('\n')
return strings.TrimRight(line, "\n"), err
}
func ReadInt(reader *bufio.Reader) (int, error) {
a, err := ReadLine(reader)
if err != nil {
return -1, err
}
num, _ := strconv.Atoi(a)
return num, err
}
func ReadArray(reader *bufio.Reader) ([]int, error) {
line, err := ReadLine(reader)
if err != nil {
return nil, err
}
strs := strings.Split(line, " ")
nums := make([]int, len(strs))
for i, s := range strs {
nums[i], _ = strconv.Atoi(s)
}
return nums, err
}
1131. 拯救大兵瑞恩
1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。
瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。
迷宫的外形是一个长方形，其南北方向被划分为 $N$ 行，东西方向被划分为 $M$ 列， 于是整个迷宫被划分为 $N×M$ 个单元。
每一个单元的位置可用一个有序数对 （单元的行号，单元的列号） 来表示。
南北或东西方向相邻的 $2$ 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。
注意： 门可以从两个方向穿过，即可以看成一条无向边。
迷宫中有一些单元存放着钥匙，同一个单元可能存放 多把钥匙，并且所有的门被分成 P 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即 $(N,M)$ 单元里，并已经昏迷。
迷宫只有一个入口，在西北角。
也就是说，麦克可以直接进入 $(1,1)$ 单元。
另外，麦克从一个单元移动到另一个相邻单元的时间为 $1$ ，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。
输入格式
第一行有三个整数，分别表示 N,M,P 的值。
第二行是一个整数 k，表示迷宫中门和墙的总数。
接下来 $k$ 行，每行包含五个整数， $X_{i1},Y_{i1},X_{i2},Y_{i2},G_i$ ：当 $G_i≥1$ 时，表示 $(X_{i1},Y_{i1})$ 单元与 $(X_{i2},Y_{i2})$ 单元之间有一扇第 $G_i$ 类的门，当 $G_i=0$ 时，表示 $(X_{i1},Y_{i1})$ 单元与 $(X_{i2},Y_{i2})$ 单元之间有一面不可逾越的墙。
接下来一行，包含一个整数 $S$ ，表示迷宫中存放的钥匙的总数。
接下来 $S$ 行，每行包含三个整数 $X_{i1},Y_{i1},Q_i$ ，表示 $(X_{i1},Y_{i1})$ 单元里存在一个能开启第 $Q_i$ 类门的钥匙。
输出格式
输出麦克营救到大兵瑞恩的最短时间。
如果问题无解，则输出 -1。
数据范围
- $|X_{i1}−X_{i2}|+|Y_{i1}−Y_{i2}|=1$
- $0≤G_i≤P$
- $1≤Q_i≤P$
- $1≤N,M,P≤10$
- $1≤k≤150$
输入样例：
4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1
输出样例：
14
样例解释：
迷宫如下所示：
解法一
一开始参考了 y 总的 0-1BFS 的做法，将拿起钥匙看作权值为 0 的点，向其他方向扩展看作权值为 1 的点，但是后来发现这种思路会比较绕，没有必要。
其实完全可以直接使用简单的 BFS 就可以解决，只需要在 BFS 的状态上加一维状态，表示当前位置手上拥有钥匙的状态（状态压缩），然后在 bfs 过程中，如果房间有钥匙就直接拿起来，因为拿起钥匙并没有消耗，状态也不会变差。具体代码实现如下
import java.util.*;
import java.io.*;
class Main {
static int INF = 0x3f3f3f3f;
static int[] dir = {1, 0, -1, 0, 1};
static int N, M, P, K, S;
// 第 i 个房间的钥匙
static int[] key;
// 邻接矩阵，权值为门的种类
static int[][] w;
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);
N = in[0]; M = in[1]; P = in[2];
K = read(br)[0];
w = new int[N * M + 1][N * M + 1];
key = new int[N * M + 2];
for (int i = 0; i <= N * M; i++) {
Arrays.fill(w[i], -1);
}
for (int i = 0; i < K; i++) {
int[] t = read(br);
int a = flat(t[0], t[1]);
int b = flat(t[2], t[3]);
int g = t[4];
// a,b 两点之间有门或者墙
w[a][b] = w[b][a] = g;
}
S = read(br)[0];
for (int i = 0; i < S; i++) {
int[] t = read(br);
key[flat(t[0], t[1])] |= 1 << t[2];
}
out.println(bfs());
out.flush();
}
public static int bfs() {
// 最短距离以及手上钥匙的状态
Deque<int[]> queue = new ArrayDeque<>();
int[][] dis = new int[N * M + 1][1 << (P + 1)];
for (int i = 0; i < N * M + 1; i++) {
Arrays.fill(dis[i], INF);
}
boolean[][] vis = new boolean[N * M + 1][1 << (P + 1)];
dis[1][key[1]] = 0;
queue.offer(new int[] {1, key[1]});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int[] t = unflat(cur[0]);
int i = t[0], j = t[1];
int st = cur[1];
if (vis[cur[0]][st]) {
continue;
}
vis[cur[0]][st] = true;
if (cur[0] == N * M) {
return dis[cur[0]][cur[1]];
}
for (int k = 0; k < 4; k++) {
int nx = i + dir[k];
int ny = j + dir[k + 1];
int nn = flat(nx, ny);
if (nx < 1 || nx > N || ny < 1 || ny > M) {
continue;
}
// 墙或者没有对应的钥匙
if (w[cur[0]][nn] == 0 || (w[cur[0]][nn] != -1 && ((st >>> w[cur[0]][nn]) & 1) == 0)) {
continue;
}
int nst = st | key[nn];
if (dis[nn][nst] > dis[cur[0]][st] + 1) {
dis[nn][nst] = dis[cur[0]][st] + 1;
queue.offer(new int[] {nn, nst});
}
}
}
return -1;
}
public static int flat(int x, int y) {
return (x - 1) * M + y;
}
public static int[] unflat(int i) {
return new int[] {(i + M - 1) / M, (i - 1) % M + 1};
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
public class AcWing1131_拯救大兵瑞恩 {
public static void main(String[] args) throws Exception {
// 输入重定向
System.setIn(new FileInputStream("./input.txt"));
new Main().main();
}
}
1134. 最短路计数
给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1$ 到 $N$ 。
问从顶点 $1$ 开始，到其他每个点的最短路有几条。
输入格式
第一行包含 $2$ 个正整数 $N,M$ ，为图的顶点数与边数。
接下来 $M$ 行，每行两个正整数 $x,y$ ，表示有一条顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。
输出格式
输出 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出对 $100003$ 取模后的结果即可。
如果无法到达顶点 $i$ 则输出 $0$ 。
数据范围
- $1≤N≤10^5$
- $1≤M≤2×10^5$
输入样例：
5 7
1 2
1 3
2 4
3 4
2 3
4 5
输出样例：
1
2
4
解法一
求最短路条数，很显然是一个动态规划题，结合了最短路。
一开始没想明白最短路更新和数量统计的关系，做了两遍 BFS。第一遍计算出最短路，第二遍利用最短路统计个数。
比较直白，没啥好说的。
两遍 BFS 的写法
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
var INF = int(0x3f3f3f3f)
var MOD = 100003
var idx int
var h []int
var e []int
var ne []int
func add(a, b int) {
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx++
}
func main() {
// f, _ := os.Open("./input.txt")
// reader := bufio.NewReader(f)
var reader = bufio.NewReader(os.Stdin)
in := ReadArray(reader)
N, M := in[0], in[1]
idx = 0
h = make([]int, N+1)
for i := 0; i <= N; i++ {
h[i] = -1
}
e = make([]int, 2*M+1)
ne = make([]int, 2*M+1)
for i := 0; i < M; i++ {
t := ReadArray(reader)
add(t[0], t[1])
add(t[1], t[0])
}
var queue []int
vis := make([]bool, N+1)
dis := make([]int, N+1)
for i := 0; i <= N; i++ {
dis[i] = INF
}
queue = append(queue, 1)
dis[1] = 1
for len(queue) > 0 {
i := queue[0]
queue = queue[1:]
if vis[i] {
continue
}
vis[i] = true
for j := h[i]; j != -1; j = ne[j] {
k := e[j]
dis[k] = Min(dis[k], dis[i]+1)
queue = append(queue, k)
}
}
queue = make([]int, 0)
queue = append(queue, 1)
vis = make([]bool, N+1)
// dp[i]: 从 1 到 i 的最短路条数
dp := make([]int, N+1)
dp[1] = 1
for len(queue) > 0 {
i := queue[0]
queue = queue[1:]
if vis[i] {
continue
}
vis[i] = true
for j := h[i]; j != -1; j = ne[j] {
k := e[j]
if dis[i]+1 == dis[k] {
dp[k] = (dp[k] + dp[i]) % MOD
}
queue = append(queue, k)
}
}
for i := 1; i <= N; i++ {
fmt.Println(dp[i])
}
}
func Min(a, b int) int {
if a < b {
return a
}
return b
}
func ReadLine(reader *bufio.Reader) string {
line, _ := reader.ReadString('\n')
return strings.TrimRight(line, "\n")
}
func ReadInt(reader *bufio.Reader) int {
num, _ := strconv.Atoi(ReadLine(reader))
return num
}
func ReadArray(reader *bufio.Reader) []int {
line := ReadLine(reader)
strs := strings.Split(line, " ")
nums := make([]int, len(strs))
for i, v := range strs {
nums[i], _ = strconv.Atoi(v)
}
return nums
}
解法二
类似的计数题其实之前也遇到过，11. 背包问题求方案数 这题就是类似的，不过这里把转移放在了最短路中。
题目给的图是存在环的，直接 dp 肯定不行，不满足拓扑序。但是实际上这里我们在图上用 bfs 求最短路时的出队节点顺序是满足拓扑序的，一层一层的更新，出队的点最短路都是确定的，不存在环，所以可以直接在 bfs 最短路过程中转移。同理 dijkstra 的最短路序列也是满足拓扑序的，每个节点出队列时最短路就确定了，只出队一次，不会回头更新之前的状态，也不存在环。
spfa 这里是不行的，节点会多次出队入队，队首节点最短路并不确定，还可能会被其他节点更新，存在环。如果节点存在负环可以先 spfa 求出最短路拓扑序，然后再 dp 求条数
$dp$ 根据 $dis$ 的值进行转移
-
当 $dis[i]+1 = dis[k]$ 时，说明两条路路径相等，直接累加起来， $dp[k] = dp[k] + dp[i]$ 。
-
当 $dis[i]+1 < dis[k]$ 时，说明有更短的路到 k，直接覆盖之前计数， $dp[k] = dp[i]$ 。
package main
import (
"bufio"
"os"
"strconv"
"strings"
)
var INF = int(0x3f3f3f3f)
var MOD = 100003
var idx int
var h []int
var e []int
var ne []int
func add(a, b int) {
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx++
}
func main() {
// f, _ := os.Open("./input.txt")
// reader := bufio.NewReader(f)
var reader = bufio.NewReader(os.Stdin)
var writer = bufio.NewWriter(os.Stdout)
in := ReadArray(reader)
N, M := in[0], in[1]
idx = 0
h = make([]int, N+1)
for i := 0; i <= N; i++ {
h[i] = -1
}
e = make([]int, 2*M+1)
ne = make([]int, 2*M+1)
for i := 0; i < M; i++ {
t := ReadArray(reader)
add(t[0], t[1])
add(t[1], t[0])
}
var queue []int
dis := make([]int, N+1)
for i := 0; i <= N; i++ {
dis[i] = INF
}
dis[1] = 1
// dp[i]: 从 1 到 i 的最短路条数
dp := make([]int, N+1)
queue = append(queue, 1)
dp[1] = 1
for len(queue) > 0 {
i := queue[0]
queue = queue[1:]
for j := h[i]; j != -1; j = ne[j] {
k := e[j]
if dis[i]+1 == dis[k] { // 累加
dp[k] = (dp[k] + dp[i]) % MOD
} else if dis[i]+1 < dis[k] { // 有更小的，覆盖掉
dp[k] = dp[i]
dis[k] = dis[i] + 1
queue = append(queue, k) // 只入队一次，最短路确定
}
}
}
for i := 1; i <= N; i++ {
writer.WriteString(strconv.Itoa(dp[i]))
writer.WriteString("\n")
}
writer.Flush()
}
func Min(a, b int) int {
if a < b {
return a
}
return b
}
func ReadLine(reader *bufio.Reader) string {
line, _ := reader.ReadString('\n')
return strings.TrimRight(line, "\n")
}
func ReadInt(reader *bufio.Reader) int {
num, _ := strconv.Atoi(ReadLine(reader))
return num
}
func ReadArray(reader *bufio.Reader) []int {
line := ReadLine(reader)
strs := strings.Split(line, " ")
nums := make([]int, len(strs))
for i, v := range strs {
nums[i], _ = strconv.Atoi(v)
}
return nums
}
383. 观光
“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。
比荷卢经济联盟有很多公交线路。每天公共汽车都会从一座城市开往另一座城市。沿途汽车可能会在一些城市（零或更多）停靠。
旅行社计划旅途从 $S$ 城市出发，到 $F$ 城市结束。
由于不同旅客的景点偏好不同，所以为了迎合更多旅客，旅行社将为客户提供多种不同线路。
游客可以选择的行进路线有所限制，要么满足所选路线总路程为 $S$ 到 $F$ 的最小路程，要么满足所选路线总路程仅比最小路程多一个单位长度。
如上图所示，如果 $S=1$ ， $F=5$ ，则这里有两条最短路线 1→2→5,1→3→5，长度为 $6$ ；有一条比最短路程多一个单位长度的路线 1→3→4→5，长度为 $7$ 。
现在给定比荷卢经济联盟的公交路线图以及两个城市 $S$ 和 $F$ ，请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。
输入格式
第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $N$ 和 $M$ ，分别表示总城市数量和道路数量。
接下来 $M$ 行，每行包含三个整数 $A,B,L$ ，表示有一条线路从城市 $A$ 通往城市 $B$ ，长度为 $L$ 。
需注意，线路是 单向的，存在从 A 到 B 的线路不代表一定存在从 B 到 A 的线路，另外从城市 A 到城市 B 可能存在多个不同的线路。
接下来一行，包含两个整数 $S$ 和 $F$ ，数据保证 $S$ 和 $F$ 不同，并且 $S、F$ 之间至少存在一条线路。
输出格式
每组数据输出一个结果，每个结果占一行。
数据保证结果不超过 $10^9$ 。
数据范围
- $2≤N≤1000$
- $1≤M≤10000$
- $1≤L≤1000$
- $1≤A,B,S,F≤N$
输入样例：
2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
4 1
输出样例
3
2
解法一
和上一题类似，但是这里需要求「次短路」计数，我们可以在前面的基础上增加一维代表次短路，然后将每个点的最短路和次短路都放入 Dijkstra 中迭代更新。
$dis[i][0/1]$ 代表 $s$ 到达 $i$ 的最短路和次短路长度， $cnt[i][0/1]$ 代表 $s$ 到达 $i$ 的最短路和次短路条数，然后分情况讨论。
枚举 $i$ 点出边：
- $dis[j][0] > w_{ij} + v_{si}$ ，说明找到了 $s\rightarrow j$ 更短的最短路，之前的最短路变为次短路
- $dis[j][0] = w_{ij} + v_{si}$ ，找到一条相同的最短路，累加
- $dis[j][1] > w_{ij} + v_{si}(dis[i][0] \leq w_{ij} + v_{si})$ ，找到了更短的次短路
- $dis[j][1] = w_{ij} + v_{si}$ ，找到一条相同的次短路，累加
其实我们可以发现：
- 一个点的最短路一定是由上一个节点的最短路演化而来
- 一个点的次短路可能是由上一个点的最短路来，也有可能由上一个点的次短路而来
package main
import (
"bufio"
"container/heap"
"fmt"
"os"
"strconv"
"strings"
)
var INF = int(0x3f3f3f3f)
var h []int
var e []int
var ne []int
var w []int
var idx int
func Add(a, b, c int) {
w[idx] = c
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx++
}
func main() {
reader := bufio.NewReader(os.Stdin)
T := ReadArray(reader)[0]
for ; T > 0; T-- {
in := ReadArray(reader)
N, M := in[0], in[1]
idx = 0
h = make([]int, N+1)
e = make([]int, M+1)
ne = make([]int, M+1)
w = make([]int, M+1)
for i := 0; i < len(h); i++ {
h[i] = -1
}
for i := 0; i < M; i++ {
t := ReadArray(reader)
Add(t[0], t[1], t[2])
}
sf := ReadArray(reader)
S, F := sf[0], sf[1]
fmt.Println(Dijkstra(S, F, N))
}
}
func Dijkstra(s, f, n int) int {
var pq NodeHeap
dis := make([][2]int, n+1)
cnt := make([][2]int, n+1)
vis := make([][2]bool, n+1)
heap.Push(&pq, &Node{s, 0, 0})
for i := 0; i <= n; i++ {
dis[i][0] = INF
dis[i][1] = INF
}
cnt[s][0] = 1
dis[s][0] = 0
for len(pq) > 0 {
cur := heap.Pop(&pq).(*Node)
i, v, t := cur.i, cur.v, cur.t
if vis[i][t] {
continue
}
vis[i][t] = true
// i 出边
for j := h[i]; j != -1; j = ne[j] {
if dis[e[j]][0] > w[j]+v { // 最短路变为次短路
dis[e[j]][1] = dis[e[j]][0]
cnt[e[j]][1] = cnt[e[j]][0] // 历史最短路覆盖次短路 cnt
dis[e[j]][0] = w[j] + v
cnt[e[j]][0] = cnt[i][t] // 新的最短路覆盖历史最短路 cnt
heap.Push(&pq, &Node{e[j], dis[e[j]][0], 0})
heap.Push(&pq, &Node{e[j], dis[e[j]][1], 1})
} else if dis[e[j]][0] == w[j]+v { // 找到一条新的最短路
cnt[e[j]][0] += cnt[i][t]
} else if dis[e[j]][1] > w[j]+v { // 找到更短的次短路
dis[e[j]][1] = w[j] + v
cnt[e[j]][1] = cnt[i][t] // 新次短路覆盖次最短路 cnt
heap.Push(&pq, &Node{e[j], dis[e[j]][1], 1})
} else if dis[e[j]][1] == w[j]+v {
cnt[e[j]][1] += cnt[i][t]
}
}
}
res := cnt[f][0]
if dis[f][1] == dis[f][0]+1 {
res += cnt[f][1]
}
return res
}
type Node struct {
i int
v int
t int
}
type NodeHeap []*Node
func (h NodeHeap) Len() int { return len(h) }
// 小顶堆
func (h NodeHeap) Less(i, j int) bool { return h[i].v < h[j].v }
func (h NodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x interface{}) {
// Push 和 Pop 使用 pointer receiver 作为参数，
// 因为它们不仅会对切片的内容进行调整，还会修改切片的长度。
*h = append(*h, x.(*Node))
}
func (h *NodeHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func ReadLine(reader *bufio.Reader) string {
line, _ := reader.ReadString('\n')
return strings.TrimRight(line, "\n")
}
func ReadArray(reader *bufio.Reader) []int {
line := ReadLine(reader)
strs := strings.Split(line, " ")
nums := make([]int, len(strs))
for i := 0; i < len(strs); i++ {
nums[i], _ = strconv.Atoi(strs[i])
}
return nums
}
func init() {
os.Stdin, _ = os.Open("./input.txt")
}
342. 道路与航线
略。此题解法有点复杂，用的 SPFA 卡过的，以后有时间再来想吧