单源最短路问题
浅浅总结一下给自己写个题解合集，咕咕了两道大难题，遇到等死就行了
知识回顾：
边权均非负的情况
|___________
| |朴素dijkstra(在稠密图上效率更高)
| |时间复杂度O(n^2)
| |堆优化版dijkstra(稀疏图上效率更高)
| |时间复杂度O(mlog(n))
|
有负权边的情况
|____________
|Bellman ford(忽略)
|Spfa 平均时间复杂度O(m)
|最坏情况和朴素djikstra一样是O(mn)
|正权边就别用，用就是找死--关于spfa 它死了
此外需要注意的情况：如果是最短路中有环的话这些方法依旧可以用
但如果权重在点上，且有环，要求最大值or最小值那么就只能用spfa。dijkstra会出问题
bfs和dijkstra自带拓扑，如果求解的方案问题非拓扑，那别用spfa用dijkstra
-
Dijkstra求最短路模版-堆优化-O(mlogn)：
与spfa的区别：dijkstra的st表示的是访问过的点就不访问了，spfa的st表示点在不在队列里。dijkstra用heap，spfa用queue。
小根堆：priority_queue<PII, vector<PII>, greater <PII>> heap;
优先队列能够表示堆，可弹出堆顶，大根堆小根堆都能建立，上面这是小根
下面这个是大根
priority_queue<PII> heap;
从源点开始，将源点的距离设为零并将其加入优先队列。在算法的每一步，从优先队列中取出具有最小估计距离的节点，然后遍历该节点的所有出边，尝试通过这些边更新邻接节点的距离。如果邻接节点的距离被更新，它们将以新的距离重新进入优先队列。这个过程持续进行，直到优先队列为空。
#include <bits/stdc++.h>
using namespace std;
const int N=150010;
typedef pair<int, int> PII;
int n,m; // 点 边数量
int d[N]; //存储所有点到1号点距离
int h[N], ne[N], e[N], w[N], idx;//邻接表存储所有边
priority_queue<PII, vector<PII>, greater <PII>> heap;
bool st[N]; //存每个点最短距离是否已确定，减少重复计算
// 开始默写
void add(int a,int b, int c)
{
e[idx]=b, ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dijkstra()
{
memset(d,0x3f,sizeof d);
d[1]=0;
heap.push({0,1}); //first存距离，second存节点编号
while (heap.size())
{
//取出堆顶，最小距离值
auto t = heap.top();
heap.pop();
int num = t.second,distance = t.first;
//判断是否属于最短路径，减少计算量
if (st[num]) continue;
st[num]=true;
//更新新的距离
for( int i=h[num]; i != -1;i = ne[i])
{
//
int j = e[i];
/* 这个和下面两行替换都能ac
都表达的是更新距离，入队新最小距离点，但这个要更快点
因为没有把未更新的d[j]都塞进去
if(d[j]>d[num]+w[i])
{
d[j]=d[num]+w[i];
heap.push({d[j],j});
}
*/
d[j]=min(d[j],distance+w[i]);
heap.push({d[j], j});
}
}
if (d[n]==0x3f3f3f3f) return -1;
return d[n];
}
//全是默写
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
cout << dijkstra() << endl;
return 0;
}
-
Dijkstra 稠密图 O(n^2)
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m,g[N][N],dist[N];
bool st[N];
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 1;j<=n;j++)
if(!st[j] && (t== -1 || dist[j]<dist[t])) t=j;
st[t]=true;
for(int j = 1; j<= n; j++) dist[j] = min(dist[j],dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
for (int i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);
}
cout << dijkstra() <<endl;
return 0;
}
-
Spfa求最短路模版：
当一个节点的最短距离估计被更新后，该节点（如果当前不在队列中）会被加入队列。接着，算法从队列中取出节点，检查所有出边，并尝试通过这些边来更新邻接节点的距离估计。如果成功更新了邻接节点的距离，且这些节点不在队列中，它们也会被加入队列。这个过程持续进行，直到队列为空，从而确保所有可能的最短路径都被探索过。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=100100;
//背诵内容
int n,m;//n点m边
int w[N],e[N],ne[N],h[N],idx;//链表存图
int st[N],dist[N];//省重复计算的状态和距离
//背诵内容
void add(int a,int b, int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
//spaf模版 背诵内容
int spfa()
{
//初始化dist
memset(dist, 0x3f, sizeof dist);
dist[1]=0;
//初始化队列和状态，点1压入队列
queue<int> q;
q.push(1);
st[1]=true;
//队列模版
while (q.size())
{//取队头值
auto t = q.front();
q.pop();
//取出来之后就不在队列里了
st[t] = false;
//沿链表拓展
for (int i = h[t];i!=-1;i=ne[i])
{
int j=e[i];
//判断新旧距离大小
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
//更新短距入队更新状态
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
}
int res = spfa();
if(res>0x3f3f3f3f/2) puts("impossible");
else cout << res <<endl;
return 0;
}
-
求无向无权图起点到每个点最短路方案数模版
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010, M = 400010, mod = 100003;
int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs()
{
queue<int> q;
q.push(1);
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
cnt[1] = 1; //初始化方案数
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t];~i; i= ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q.push(j);
}
//重点就在这里
else if(dist[j] == dist[t] + 1) //如果邻边距离一样则是当前最短路共同方案点
{
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m -- )
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bfs();
for(int i = 1; i <= n; i ++ ) cout << cnt[i] << endl;
return 0;
}
-
接下来是单源最短路的建图方式、单源最短路的综合应用、单源最短路的扩展应用的题解思路
单源最短路的建图方式（简单单源最短路问题）
AcWing 1129. 热浪 （spfa求最短路）
AcWing 1128. 信使 (求一个点抵达其他所有点的最短时间，就是做一遍单源最短路，然后给出dist中最大值) (为了代码最短用的Floyd)(在这个题中floyd要初始化点自己到自己距离为0)
AcWing 1127. 香甜的黄油
(求任一点到其他所有点的最小距离和) spfa O(nm) 堆优化dijkstra O(nmlogn)
AcWing 1126. 最小花费（乘法类路径最小值，每过一个人都会收z%的手续费，求至少要多少钱才够目标手里100元）
AcWing 920. 最优乘车（应用类构造最短路径，求的是最小换乘次数，要按题意转换边的构建方式）
AcWing 903. 昂贵的聘礼(咕咕咕)
单源最短路的综合运用
AcWing 1135. 新年好（先对每个点都做一次最短路，然后查表bfs五个目标点，求120种组合的最小值）
AcWing 340. 通信线路(咕咕咕)
AcWing 342. 道路与航线（拓扑排序+dijkstra）
AcWing 341. 最优贸易（权在点上，让求买入减卖出的最大值。所以就是求前k段买入最小值和后k+1段卖出最大值的差值。因此用spfa正求一遍最小值，返求一遍最大值，然后枚举一遍所有点作为分界点求最大值。不能用dijkstra的原因是存在环，会导致更新出错）
单源最短路的扩展应用
AcWing 1137. 选择最佳线路（多起点最短路问题，可以添加一个虚拟源点，这个点到所有起点的距离为0。对应的，对于多终点问题也可以弄一个虚拟终点）
AcWing 1131. 拯救大兵瑞恩 (dp和最短路问题的结合，先分析dp的状态，由于可能存在回路所以dp无法保证状态转移前的值被计算过，所以要使用最短路的思路进行状态转移)
AcWing 1134. 最短路计数（最短路求方案数问题，可以用bfs和dijkstra做，不能用spfa，因为bfs和dijkstra具备拓扑性而spfa不。求方案数就是在判断到d[j]=d[t]+w[i]时对cnt进行记录）
AcWing 383. 观光(最短路按条件求方案数，dijkstra，更新的时候分情况讨论)
题解：
AcWing 1129. 热浪
裸的单源最短路
这题不卡数据，普dijkstra优dijkstra和Spfa都可以做
y总用的循环队列，其实用普通队列也行，队列里存的点数最多为n。
共1~T个城镇，起点终点是单向边，其他无向边
起点Ts，终点Te，C条无向边，花费Ci，无向边起点Rs终点Re
求花费最少路（最短边权）
输入格式
第一行:4个由空格隔开的整数: T,C,Ts,Te
第2到第Ci+1行描述第i条道路，包含3个由空格隔开的整数: Rs,Re,Ci。
输出格式
一个单独的整数表示从 Ts 到 Te的最小总费用。
数据保证至少存在一条道路。
数据范围
1≤T≤2500,
1≤C≤6200,
1≤Ts,Te,Rs,Re≤T,
1≤Ci≤1000
输入样例：
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例：
7
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2600, M = 6200 * 2 + 10;
int n,m,S,T; //点边起点终点
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];//距离，循环队列，判重数组
bool st[N]; //判断谁在队列里
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist); //初始化距离为正无穷
dist[S] = 0; //起点距离初始化为0
int hh = 0, tt = 1;
q[0] = S, st[S] = true; //把起点放进队列
while(hh != tt) //循环队列的while是hh!=tt
{
int t = q[hh++];
if(hh == N) hh = 0; //循环队列抵达N则变回开头
st[t] = false; //出队了，标记清除
for(int i = h[t]; ~i; i = ne[i]) //接着扩展队头元素
{
int j = e[i];
if( dist[j] > dist[t] + w[i]) //如果能更新就更新
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
q[tt ++ ] = j;
if(tt == N) tt = 0; //入队时考虑队尾是不是到N了，循环到开头
st[j] = true;
}
}
}
}
}
int main()
{
cin >> n >> m >> S >> T;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a,b,c), add(b,a,c);
}
spfa();
cout << dist[T] << endl;
return 0;
}
AcWing 1128. 信使
n个哨所m个边，其中有一个指挥部，求指挥部通知到所有哨所的最短时间。
输入格式
第 1行有两个整数 n 和 m，中间用 1 个空格隔开，分别表示有 n 个哨所和 m 条通信线路。
第 2 至 m+1 行：每行三个整数 i、j、k，中间用 1 个空格隔开，表示第 i 个和第 j 个哨所之间存在 双向 通信线路，且这条线路要花费 k 天
输出格式
一个整数，表示完成整个送信过程的最短时间。
如果不是所有的哨所都能收到信，就输出-1。
数据范围
≤n≤100,
1≤m≤200,
1≤k≤1000
输入样例：
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例：
11
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N];
int main()
{
cin >> n >> m;
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= n; i ++ ) d[i][i] = 0;
for(int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
d[a][b] = d[b][a] = min(d[a][b], c);//有重边选最短
}
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
int res = 0;
for(int i = 1; i <= n; i ++) //遍历一下1号点到其他所有点的距离
if(d[1][i] == INF)
{
res = -1;
break;//有抵达不了的就终止
}
else res = max(res, d[1][i]);
cout << res << endl;
return 0;
}
AcWing 1127. 香甜的黄油
spfa求任一点到其他所有点的最小距离
给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场
输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。
输出格式
共一行，输出奶牛必须行走的最小的距离和。
数据范围
1≤N≤500,
2≤P≤800
1≤C≤1450
1≤D≤255
输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int n, p, m; //奶牛、牧场、边
int id[N];
int h[N], e[M], ne[M], w[M], idx;
int dist[N], q[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int spfa(int start)
{
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
queue<int> q;
q.push(start);
st[start] = true;
while(q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i=ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
int res = 0;
for(int i = 0; i < n; i ++ )
if(dist[id[i]] == INF) return INF;//牛不可达，返回正无穷
else res += dist[id[i]];
return res;
}
int main()
{
cin >>n >>p >>m;
for(int i = 0; i < n; i ++ ) cin >> id[i];
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a,b,c), add(b,a,c);
}
int res = INF;
//让spfa返回所有奶牛到点i的距离之和
for(int i = 1; i <= p; i ++) res = min(res, spfa(i));
cout << res << endl;
return 0;
}
AcWing 1126. 最小花费
起点给终点转钱，经过每条边要收z%的手续费，求起点转多少钱才能给终点100
换言之，从终点出发，每条边×(1+z)，求到达起点最小是多少钱
输入格式
第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。
以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 ( z<100 )。
最后一行输入两个正整数 A,B。数据保证 A与 B 之间可以直接或间接地转账。
输出格式
输出 A 使得 B 到账 100 元最少需要的总费用。
数据范围
1≤n≤2000,
m≤10^5
输入样例：
3 3
1 2 1
2 3 2
1 3 3
1 3
输出样例：
103.07153164
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, m;
double g[N][N];
double dist[N];
bool st[N];
int S, T;
void dijkstra()
{
dist[S] = 1;
for(int i = 1; i <= n; i ++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
if(!st[j] && (t == -1 || dist[t] < dist[j]))
t = j;
st[t] = true;
for(int j = 1; j <= n; j ++ )
dist[j] = max(dist[j], dist[t] * g[t][j]);
}
}
int main()
{
scanf("%d%d", &n, &m);
while(m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
double z = (100.0 - c)/100;
g[a][b] = g[b][a] = max(g[a][b], z);
}
cin >> S >> T;
dijkstra();
printf("%.8lf\n", 100/dist[T]);
return 0;
}
AcWing 920. 最优乘车
乘公交车，公交车站标号1-n，有m条线路，求从站1坐到站n的最小换乘次数
每一条线路都可以看做是一条单向边，每条线路中后面的点都可以由前面的点在一次换乘时抵达，因此一条线路中前面的点到后面的距离记作1，然后构图，再求1到n的最小距离即可
另外这题踩坑了…
边的数量要开够，不然结果是错的，过不了最后一个数据
输入格式
第一行有两个数字 M 和 N，表示开通了 M 条单程巴士线路，总共有 N 个车站。
从第二行到第 M+1 行依次给出了第 1 条到第 M 条巴士线路的信息，其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。
输出格式
共一行，如果无法乘巴士从饭店到达 S 公园，则输出 NO，否则输出最少换乘次数，换乘次数为 0 表示不需换车即可到达。
数据范围
1≤M≤100,
2≤N≤500
输入样例：
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2
踩坑了…
边的数量要开够，不然结果是错的，过不了最后一个数据
//对每条公交线路建单向边，边长为1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream> //由于公交站没告诉，所以用这个来读
#include <queue>
using namespace std;
const int N = 510, M = 250010;
int n,m;
int dist[N];
int stop[N];//公交线路的站牌
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
bool st1[N];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = 1, h[a] = idx ++;
}
void bfs()
{
memset(dist, 0x3f, sizeof dist);
queue<int> q;
q.push(1);
dist[1] = 0;
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> m >> n;//n站，m边
string line;
getline(cin, line); //从标准输入流cin读取一行数据并存到line
//上面这里是把回车给读掉
while(m--)
{
getline(cin, line);
stringstream ssin(line); //相当于scanf
int cnt = 0, p; //站牌下标，编号
while(ssin >> p) stop[cnt++] = p;
for(int i = 0; i < cnt; i ++ )
for(int j = i + 1; j < cnt; j ++ )
add(stop[i], stop[j], 1);
}
bfs();
if (dist[n] > 0x3f3f3f3f /2) cout << "NO" << endl;
else if(n == 1) cout << "0" << endl;
else cout << dist[n] - 1 << endl;
return 0;
}
AcWing 1135. 新年好
有个人要去abcde点拜访亲戚，这些亲戚分别在一个公交站点，每个公交站都是一个点，要求遍历所有亲戚站牌的最小距离。
/*先预处理出从1abcde出发到其他所有点的单元最短路径
dfs所有摆放顺序，对于每一种顺序可以通过查表的方式算出最短距离
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5e4+10, M = 2e5 + 10;
typedef pair<int, int> PII;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[6][N];
bool st[N], st1[6];
int source[6];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void dijkstra(int start, int dist[])
{
priority_queue<PII, vector<PII>, greater <PII>> heap;
memset(st, 0, sizeof st);
memset(dist, 0x3f, N * 4);
dist[start] = 0;
heap.push({0, start});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int num = t.second;
if(st[num]) continue;
st[num] = true;
for(int i = h[num]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[num] + w[i])
{
dist[j] = dist[num] + w[i];
heap.push({dist[j],j});
}
}
}
}
void spfa(int start, int dist[])
{
queue<int> q;
memset(st, 0, sizeof st);
memset(dist, 0x3f, N * 4);
/*sizeof运算要求结果在编译时就能确定，
这里dist[]数组作为了函数参数来传递，
大小由传入的数组大小决定，不能静态确定，所以要指明大小
*/
dist[start] = 0;
q.push(start);
st[start] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
//u表示摆放亲戚数量+起点，start表示当前从哪开始，distance表示累计距离
int dfs(int u, int start, int distance)
{
if(u == 6) return distance; //表示拜访完了五个亲戚
int res = 0x3f3f3f3f; //从当前这个点u出发，距离最短的分支是多少
for(int i = 1; i <=5; i ++) //表示从start出发遍历其他source
{
if(!st1[i]) //如果当前这个亲戚没有拜访过
{
int next = source[i];
st1[i] = true;
res = min(res, dfs(u + 1, i, distance + dist[start][next]));//链式反应，拜访下一个亲戚
st1[i] = false;
}
}
return res;
}
int main()
{
cin >> n >> m;
source[0] = 1;
memset(h, -1, sizeof h);
for(int i = 1; i <= 5; i ++ ) cin >> source[i];
while(m --)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c), add(b,a,c);
}
//对每个起点都最短路一遍
//for(int i = 0; i <=5; i ++ ) spfa(source[i], dist[i]);
for(int i = 0; i <=5; i ++ ) dijkstra(source[i], dist[i]);
//dfs所有亲戚，dfs(当前位置，起点，距离)
cout << dfs(1, 0, 0) << endl;
return 0;
}
AcWing 342. 道路与航线
单源最短路径+拓扑排序。
道路之间dijkstra，航线之间拓扑序，把道路看成团，团与团之间由航线相连。
由于题意保证连通块是拓扑图，每经历一次单向边就看做去了下一个团。
- 先输入所有双向道路，然后dfs出所有联通快，计算出两个数组：id[]存储每个点属于哪些连通块，vector[HTML_REMOVED] block[]存储每个连通块里有哪些点
- 输入所有航线，同时统计出每个连通块的入度。
- 按拓扑序依次处理每个连通块。先将所有入度为0的连通块的编号加入队列中。
- 每次从队头取出一个连通块的编号
- 将该
block[bid]中的所有点加入堆中，然后对堆中所有点做dijkstra算法。 - 每次取出堆中距离最小的点ver。
- 然后遍历ver的所有邻点，如果
id[ver] == id[j]说明在连通块内部，那么就更新j，将j插入堆中。如果id[ver]!=id[j]，则将id[j]这个连通块的入度减1，如果减到0了则插入拓扑排序的队列中。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25010, M = 150010;
int n, mr, mp, S; //城镇数量，road数量，航线数量，起点
int h[N], e[M], ne[M], w[M], idx;
int id[N]; //每个点属于哪些块
vector<int> block[N]; //连通块包含哪些点
int bid; //连通块id
int dist[N]; //到起点距离
int din[N];//存每个航线的入度
bool st[N];
queue<int> q;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
//搜索连通块，标记处理u，然后对u的所有邻边进行搜索，如果没访问过就接着搜
void dfs(int u, int bid)
{
id[u] = bid;
block[bid].push_back(u);
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!id[j]) dfs(j, bid);
}
}
void dijkstra(int bid)
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
//遍历block[bid]中所有的点
for(auto ver: block[bid]) heap.push({dist[ver], ver});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y, distance = t.x;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
if(id[j] == id[ver]) heap.push({dist[j], j}); //邻边在同一连通块内则push
}
//如果新拓展的点不在同一连通块，且入度减去1后为0则给topsort入队
if(id[j] != id[ver] && --din[id[j]] == 0 ) q.push(id[j]); //id[j]表示j所在的连通块
}
}
}
void topsort()
{
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
for(int i = 1; i <= bid; i ++) //遍历所有连通块
if(din[i] == 0) q.push(i); //把所有入度为0的连通块加到队列里面
while(q.size())
{
auto t = q.front();
q.pop();
dijkstra(t); //对这一团入度为0的做起点为t的内部dijkstra，在dijkstra里会进行入度更改和拓扑入队
}
}
int main()
{
cin >> n >> mr >> mp >> S;
memset(h, -1, sizeof h);
while(mr --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a,b,c), add(b,a,c);
}
//先搜一下连通块
for(int i = 1; i <= n; i ++ )
if(!id[i]) //如果当前这个点还没有连通块id的话说明还没有被遍历过
{
dfs(i, ++ bid);
}
while(mp --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a,b,c);
din[id[b]]++; //b所在的连通块入度++
}
topsort();
for(int i = 1; i <= n; i ++)
if(dist[i] > 0x3f3f3f3f / 2) puts("NO PATH");
else cout << dist[i] << endl;
return 0;
}
AcWing341. 最优贸易
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 100010, M = 2000010;
int n, m;
int w[N];
int hs[N], ht[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
bool st[N];
queue<int> q;
void add(int h[], int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void spfa(int h[], int dist[], int type)
{
if(type == 0)//求最小值
{
memset(dist, 0x3f, sizeof dmin);
dist[1] = w[1];
q.push(1);
}
else //求最大值
{
memset(dist, -0x3f, sizeof dmax);
dist[n] = w[n];
q.push(n);
}
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(type == 0 && dist[j] > min(dist[t], w[j]) || type == 1 && dist[j] < max(dist[t], w[j]))
{
if(type == 0) dist[j] = min(dist[t], w[j]);
else dist[j] = max(dist[t], w[j]);
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n;i ++) scanf("%d", &w[i]);
memset(hs, -1, sizeof hs);
memset(ht, -1, sizeof ht);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(hs, a, b), add(ht, b, a);
if(c == 2) add(hs, b, a), add(ht, a, b);
}
spfa(hs, dmin, 0);
spfa(ht, dmax, 1);
//枚举一遍所有点作为分界点求最大值
int res = 0;
for(int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);
cout << res << endl;
return 0;
}
AcWing1137. 选择最佳线路
/*
求从多个起点到一个终点的最短路
可以在所有起点之前建一个虚拟源点，虚拟源点到所有起点的距离为0
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010, M = 21010;
int n,m,T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[0] = 0;
queue<int> q;
q.push(0);
st[0] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j=e[i];
if(dist[j] > dist[t] +w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
if(dist[T] > 0x3f3f3f3f / 2) return -1;
return dist[T];
}
int main()
{
while(scanf("%d%d%d", &n, &m, &T) != -1)
{
memset(h, -1, sizeof h);
idx = 0;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int s; //共有s个起点车站
scanf("%d", &s);
while(s --)
{
int ver; //接下来s行每行都是车站编号
scanf("%d", &ver);
add(0, ver, 0); //添加一条从虚拟原点到多个起点的长度为0的边
}
cout << spfa() << endl;
}
return 0;
}
AcWing1131. 拯救大兵瑞恩
dp转化为最短路问题
先用dp思路分析，思考在几何上的最优化问题
d(x,y,state)来表示在点(x,y)上的钥匙状态为x的最短路距离
这样的话他的转移就分为两种情况
一种是xy有钥匙，要更新state，d(x,y,state)=d(x,y,state|key)
一种是没钥匙，拓展点的情况。假设新点是(a,b)，那么d(a,b,state)=min(d(a,b,state),d(x,y,state)+1)
由于d()的状态可以看做一个图，建图如下
d(x,y,state) --> d(x,y,state|key) 距离为0
d(x,y,state) --> d(a,b,state) 距离为1
//为了方便处理输入输出。用一维数组表达二维图的点，省去二维坐标的过程。
#include <iostream>
#include <algorithm>
#include <deque> //双端队列用于双向bfs
#include <cstring>
#include <set> //用来存把哪条边加上了
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 11, M = N * N, E = 400, P = 1 << 10;
int n, m, p, k;
int h[M], e[E], ne[E], w[E], idx;
int g[N][N], key[M];
int dist[M][P];
bool st[M][P]; //判重
set<PII> edges;
void add(int a,int b, int c){
e[idx]= b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void build(){
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0,1,0,-1};
for(int i =1; i <=n; i ++ )
for(int j = 1;j <= m; j ++ )
for(int u = 0; u < 4; u ++)
{
int x = i + dx[u], y = j + dy[u];
if(x <=0 || x>n || y<=0 || y > m) continue;
int a = g[i][j], b = g[x][y];
if(!edges.count({a,b})) add(a, b, 0); //0表示ab之间可通行
}
}
int bfs()
{
memset(dist, 0x3f, sizeof dist);
dist[1][0] = 0; //1号点是起点，钥匙状态为没有钥匙，即0
deque<PII> q;
q.push_back({1, 0});
while(q.size())
{
PII t = q.front();
q.pop_front();
if(st[t.x][t.y]) continue; //如果这个点搜过就不搜了
st[t.x][t.y] = true;
if(t.x == n * m) return dist[t.x][t.y];
if(key[t.x]) //t.x是这个点的id，key[t.x]就是钥匙的state。如果这个点有钥匙。
{
int state = t.y | key[t.x]; //新的更新后的state就等于这个点已经记录的state t.y与上新的key[t.x]
if(dist[t.x][state] > dist[t.x][t.y])
{
dist[t.x][state] = dist[t.x][t.y];
q.push_front({t.x, state}); //把这个点加到队头。因为边权为0
}
}
//正常情况枚举边
for(int i = h[t.x]; ~i; i = ne[i])
{
int j = e[i];
if(w[i] && !(t.y >> w[i] - 1 & 1)) continue; //w[i]!=0为门, 判断一下state的w[i]-1位是不是1就知道有没有钥匙
if(dist[j][t.y] > dist[t.x][t.y] + 1)
{
dist[j][t.y] = dist[t.x][t.y] + 1;
q.push_back({j, t.y});
}
}
}
return -1;
}
int main()
{
cin >> n >> m >> p >> k;
for(int i = 1, t = 1; i <=n; i ++)
for(int j = 1; j <= m; j ++)
g[i][j] = t++; //每一个位置都给个编号不重样儿
memset(h,-1,sizeof h);
while(k--)
{
int x1,y1,x2,y2,c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
int a = g[x1][y1], b = g[x2][y2];
edges.insert({a,b}), edges.insert({b,a});
if(c) add(a,b,c), add(b,a,c); //如果不是墙的话建双边, c表示需要第c号钥匙
}
build();//把没有出现过的剩余的边建起来
//读钥匙
int s;
cin >> s;
while(s--)
{
int x, y, id;
cin >> x >> y >> id;
key[g[x][y]] |= 1 << id -1; //因为点xy可能存在多把钥匙，所以用|=就可以堆叠状态。1<<id-1 是为了让他从最低位开始
}
cout << bfs() << endl;
return 0;
}
AcWing1134. 最短路计数
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010, M = 400010, mod = 100003;
int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs()
{
queue<int> q;
q.push(1);
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
cnt[1] = 1; //初始化方案数
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t];~i; i= ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q.push(j);
}
//重点就在这里
else if(dist[j] == dist[t] + 1) //如果邻边距离一样则是当前最短路共同方案点
{
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m -- )
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bfs();
for(int i = 1; i <= n; i ++ ) cout << cnt[i] << endl;
return 0;
}
AcWing383. 观光
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010, M = 10010;
struct Ver {
int id, type, dist; //type是指最短路还是次短路
bool operator> (const Ver &W) const
{
return dist > W.dist;
}
};
int n,m;
int S, T;
int h[N], e[M],w[M],ne[M],idx;
int dist[N][2], cnt[N][2];
bool st[N][2];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a],h[a] = idx ++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
dist[S][0] = 0, cnt[S][0] = 1;
priority_queue<Ver, vector<Ver>, greater<Ver>> heap;
Ver start;
start.id = S, start.type = 0, start.dist = 0;
heap.push(start);
while(heap.size())
{
Ver t = heap.top();
heap.pop();
int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];
if(st[ver][type]) continue;
st[ver][type] = true;
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j][0] > distance + w[i])//如果有比最小值还小的距离
{
dist[j][1] = dist[j][0];//就将最小值转为次小值
cnt[j][1] = cnt[j][0];//将最小值的计数覆盖次小值计数
heap.push({j, 1, dist[j][1]});//将次小值压入队列
dist[j][0] = distance + w[i], cnt[j][0] = count;//更新最小路
heap.push({j, 0, dist[j][0]});
}
else if(dist[j][0] == distance + w[i]) cnt[j][0] += count;
//更新次小值
else if(dist[j][1] > distance + w[i])
{
dist[j][1] = distance + w[i], cnt[j][1] = count;
heap.push({j, 1, dist[j][1]});
}
else if(dist[j][1] == distance + w[i]) cnt[j][1] += count;
}
}
int res = cnt[T][0];
//如果最短距离+1等于次短距离
if(dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];
return res;
}
int main()
{
int cases;
cin >> cases;
while(cases--)
{
cin >> n >> m;
memset(h,-1,sizeof h);
idx = 0;
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
}
cin >> S >> T;
cout << dijkstra() << endl;
}
return 0;
}
