题目描述
给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 kk 个询问，每个询问包含两个整数 xx 和 yy，表示查询从点 xx 到点 yy 的最短距离，如果路径不存在，则输出
impossible。数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,kn,m,k。
接下来 mm 行，每行包含三个整数 x,y,zx,y,z，表示存在一条从点 xx 到点 yy 的有向边，边长为 zz。
接下来 kk 行，每行包含两个整数 x,yx,y，表示询问点 xx 到点 yy 的最短距离。
输出格式
共 kk 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出
impossible。数据范围
1≤n≤2001≤n≤200,
1≤k≤n21≤k≤n2
1≤m≤200001≤m≤20000,
图中涉及边长绝对值均不超过 1000010000。输入样例：
3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3输出样例：
impossible 1
算法求解
分析
- 注意存在负权边
- 是多源最短路径
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f;
// 用邻接矩阵存储
int d[N][N];
int n, m, k;
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()
{
scanf("%d%d%d", &n, &m, &k);
// 初试化边权
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 x, y, w;
scanf("%d%d%d",&x, &y, &w);
d[x][y] = min(d[x][y], w); // 对于重边去最小的
}
floyd();
while(k--)
{
int a, b;
scanf("%d%d", &a, &b);
if(d[a][b] > INF / 2) printf("impossible\n");
else printf("%d\n",d[a][b]);
}
return 0;
}
时间复杂度
\(O(n^3)\)
参考文章
算法分析
(y总真言，简单易懂)
f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。读入邻接矩阵，将次通过动态规划装换成从i到j的最短距离矩阵
在下面代码中，判断从a到b是否是无穷大距离时，需要进行
if(t > INF/2)判断，而并非是if(t == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，t大于某个与INF相同数量级的数即可作者：小呆呆
链接：https://www.acwing.com/solution/content/6337/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
文字性复习
Dijkstra-朴素O(n^2)
- 初始化距离数组, dist[1] = 0, dist[i] = inf;
- for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
- 将不在S中dist_min的点->t
- t->S加入最短路集合
- 用t更新到其他点的距离
Dijkstra-堆优化O(mlogm)
- 利用邻接表，优先队列
- 在priority_queue[HTML_REMOVED], greater[HTML_REMOVED] > heap;中将返回堆顶
- 利用堆顶来更新其他点，并加入堆中类似宽搜
Bellman_fordO(nm)
- 注意连锁想象需要备份, struct Edge{inta,b,c} Edge[M];
- 初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
- 松弛k次，每次访问m条边
Spfa O(n)~O(nm)
- 利用队列优化仅加入修改过的地方
- for k次
- for 所有边利用宽搜模型去优化bellman_ford算法
- 更新队列中当前点的所有出边
Floyd O(n^3)
- 初始化d
- k, i, j 去更新d
作者：竹林正在青
链接：https://www.acwing.com/solution/content/6976/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。