最短路问题
朴素版Dijkstra(稠密图)
s数组，当前已经确定最短路径的点
1 dis[1] = 0, dis[i] = 正无穷
2 for(int i = 0; i <= n; i ++)
t <- 不在s中距离最近的点
s <- t 用t更新其他点的距离（从t出去的所有的边组成的路径能不能更新其 他点的距离
1 -> t -> x;
1 ------> x;如果前一种情况的距离小于第二种就可以更新
dis[x] > dis[t] + w;给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x, y, z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1 ≤ n ≤ 500,
1 ≤ m ≤ 105,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4输出样例：
3#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int g[N][N];
int dist[N];
bool st[N];
int n, m;
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; 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] = min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while(m --){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << dijkstra();
return 0;
}堆优化版Dijkstra（稀疏图）
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1−1。
输入格式
第一行包含整数 n 和 m。
接下来 mm 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×105
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。
输入样例：
3 3
1 2 2
2 3 1
1 3 4输出样例：
3#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[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 dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});//前一个是距离，后一个是
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[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;
}Bellman_Ford(极少数情况，图中不存在负权回路(负环))
1.for(int i = 1; i <= n; i ++)
2.备份dist防止串联
3.for 所有边 a,b,w
4.dist[b] = min(dist[b], dist[a] + w)(松弛操作)
最后满足dist[b] <= dist[a] + w(三角不等式)
此算法不能存在负权回路
是否存在负权回路的验证方法
1.迭代K次(不超过k条边)的最短路的距离
2.如果第n次迭代时更新了某些边(说明存在一条最短路径有n条边，n+1个点)(说明一定存在负权回路)
一共有n个点，但是出现了n个边，根据抽屉原理，说明一定有回路存在有边数限制的最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500，
1≤m≤10000,
任意边长的绝对值不超过 10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3输出样例：
3#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 10010;
struct Edge
{
int a, b, w;
}edges[M];
int dist[N];
int backup[N];
int n, m, k;
void bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < k; i ++ ){
memcpy(backup, dist, sizeof dist);
for(int j = 0; j < m; j ++){
auto t = edges[j];
dist[t.b] = min(dist[t.b], backup[t.a] + t.w);
}
}
}
int main(){
cin >> n >> m >> k;
for(int i = 0; i < m; i ++){
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
bellman_ford();
if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else cout << dist[n] << endl;
return 0;
}SPFA(Shortest Path Faster Algorithm)（常用）
好多题可以用SPFA写Dijkstra,如果被卡数据，那么就换堆优化版本的Dijkstra
SPFA求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4输出样例：
2#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int idx, e[N], h[N], ne[N], w[N];
int dist[N];
bool st[N];
int n, m;
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[1] = 0;
queue<int>q;
q.push(1);
st[1] = true;
while(q.size()){
int 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];(注意，是dist[t])
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
while(m -- ){
int a, b, w;
cin >> a >> b >> w;
add(a, b, w);
}
int t = spfa();
if(t == 0x3f3f3f3f) puts("impossible");
else cout << t;
return 0;
}SPFA判断负环
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 mm 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 -1
2 3 4
3 1 -4输出样例：
Yes#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;
int idx, h[N], ne[M], e[M], w[M];
int dist[N], cnt[N];
bool st[N];
int n, m;
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(){
queue<int> q; //求负环时由于只需要判断负环是否存在，不需要求出路径的具体长度，因此dist数组就不需要初始化了。
for(int i = 1; i <= n; i ++){
q.push(i);
st[i] = true;
}
while(q.size()){
int 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];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
while(m -- ){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}Floyd（多源最短路）
d[k, i, j] 表示从i到j经过k个点的最短距离
d[k, i, j] = d[k - 1, i, k] + d[k - 1, k, j];可以用一重循环来将三维降低维度，降低至二维，如下：
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]);#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
void floyd(){
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 main(){
cin >> n >> m >> Q;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
while(m -- ){
int a, b, w;
cin >> a >> b >> w;
d[a][b] = min(d[a][b], w);
}
floyd();
while(Q --){
int a, b;
cin >> a >> b;
if(d[a][b] > INF / 2) puts("impossible");
else cout << d[a][b] << endl;
}
return 0;
}大众情人
人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 D~ij~；将 i 的“异性缘”定义为 1/max~j∈S(i)~{D~ij~}，其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。
本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。
输入格式：
输入在第一行中给出一个正整数 N（≤500），为总人数。于是我们默认所有人从 1 到 N 编号。
随后 N 行，第 i 行描述了编号为 i 的人与其他人的关系，格式为：
性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K其中 性别 是这个人的性别，F 表示女性，M 表示男性；K（<N 的非负整数）为这个人直接认识的朋友数；随后给出的是这 K 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 106 的正整数。
题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。
输出格式：
第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。
输入样例：
6
F 1 4:1
F 2 1:3 4:10
F 2 4:2 2:2
M 2 5:1 3:2
M 2 2:2 6:2
M 2 3:1 2:5输出样例：
2 3
4#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9, N = 510;
int n;
int sex[N], dist[N], g[N][N];
int main(){
cin >> n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) g[i][j] = 0;
else g[i][j] = INF;
for(int i = 1; i <= n; i ++){
char op[2];
int k;
cin >> op >> k;
if(*op == 'M') sex[i] = 1;
for(int j = 1; j <= k; j ++){
int a, b;
scanf("%d:%d", &a, &b);
g[i][a] = b;
}
}
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
for(int i = 1; i <= n; i ++){
dist[i] = 0;
for(int j = 1; j <= n; j ++){
if(sex[i] != sex[j]){
dist[i] = max(dist[i], g[j][i]);
}
}
}
for(int i = 0; i < 2; i ++){
int minn = 2e9;
for(int j = 1; j <= n; j ++){
if(sex[j] == i){
minn = min(minn, dist[j]);
}
}
int f = 0;
for(int j = 1; j <= n; j ++){
if(sex[j] == i && minn == dist[j]){
if(f) cout << " ";
cout << j;
f ++;
}
}
cout << endl;
}
return 0;
}