免费域名注册服务网站,全国代理网,昆明二建建设集团网站,做网上竞猜网站合法吗图论–最短路问题
邻接表
/*
e[idx]:存储点的编号
w[idx]:存储边的距离#xff08;权重#xff09;
*/
void add(int a, int b, int c) {e[idx] b;ne[idx] h[a];w[idx] ch[a] idx ;
}1.拓扑排序 给定一个 n 个点 m 条边的有向图#xff0c;点的编号是 11 到 n#xf…图论–最短路问题
邻接表
/*
e[idx]:存储点的编号
w[idx]:存储边的距离权重
*/
void add(int a, int b, int c) {e[idx] b;ne[idx] h[a];w[idx] ch[a] idx ;
}1.拓扑排序 给定一个 n 个点 m 条边的有向图点的编号是 11 到 n图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列如果拓扑序列不存在则输出 −1−1。 若一个由图中所有点构成的序列 A 满足对于图中的每条边 (x,y)x在 A中都出现在 y 之前则称 A是该图的一个拓扑序列。 输入格式 第一行包含两个整数 n 和 m。 接下来 m 行每行包含两个整数 x 和 y表示存在一条从点 x 到点 y的有向边 (x,y)。 输出格式 共一行如果存在拓扑序列则输出任意一个合法的拓扑序列即可。 否则输出 −1−1。 #include iostream
#include algorithm
#include cstring
#include queueusing namespace std;const int N 1e5 10;int n, m;// 队列
int q[N], hh, tt -1;// 邻接表
int e[N], idx, ne[N], h[N];// 入度
int d[N];void add(int a, int b) {e[idx] b;ne[idx] h[a];h[a] idx ;
}bool topsort() {for (int i 1; i n; i )if (!d[i])q[ tt] i;while (hh tt) {int tmp q[hh ];for (int i h[tmp]; i ! -1; i ne[i]) {int j e[i];d[j] --;if (!d[j])q[ tt] j;}}if (tt n-1) return true;return false;
}int main() {memset(h, -1, sizeof h);cin n m;while (m --) {int a, b;cin a b;add(a, b);d[b] ;}if (topsort()) for (int i 0; i n; i )cout q[i] ;else cout -1;return 0;
}2.Dijkstra求最短路
稠密图边很多——邻接矩阵
所有边权都是正数,单源最短路 初始化到每个节点距离为无穷inf初识节点距离dist[1] 0 迭代n轮 每次从未标记的节点中选择距离出发点最近的节点标记收录到最优路径集合中 计算刚加入节点A的临近节点B的距离不包含标记的节点。若节点A的距离加节点A到B的距离小于节点B的距离则更新节点B的距离。 给定一个 n 个点 m条边的有向图图中可能存在重边和自环所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x到点 y 的有向边边长为 z。 输出格式 输出一个整数表示 1 号点到 n 号点的最短距离。 如果路径不存在则输出 −1。 #include iostream
#include algorithm
#include cstring
#include cstdiousing namespace std;const int N 505;int n, m;// 标记
int st[N];
// 距离
int dist[N];
// 邻接矩阵
int g[N][N];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] 1;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() {memset(g, 0x3f, sizeof g);scanf(%d%d, n, m);for (int i 1; i n; i )g[i][i] 0;while (m --) {int x, y, z;scanf(%d%d%d, x, y, z);g[x][y] min(g[x][y], z);}int ans dijkstra();printf(%d, ans);return 0;
}堆优化
稀疏图点很多——邻接表
#include iostream
#include cstring
#include queue
#include algorithm
#include cstdiousing namespace std;typedef pairint, int pii;const int N 1e6 10;int n, m;// 标记避免自环
int st[N]; // 邻接表
int e[N], h[N], ne[N], w[N], idx;void add(int a, int b, int c) {e[idx] b;ne[idx] h[a];w[idx] c;h[a] idx ;
}int dist[N];int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] 0;// 小根堆 {边权(距离)编号}priority_queuepii, vectorpii, greaterpii heap;heap.push({0, 1});while (!heap.empty()) {int v heap.top().second, distance heap.top().first;heap.pop();if (st[v]) continue;st[v] 1;for (int i h[v]; i ! -1; i ne[i]) if (dist[e[i]] dist[v] w[i]){dist[e[i]] dist[v] w[i];heap.push({dist[e[i]], e[i]});}}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main() {memset(h, -1, sizeof h);scanf(%d%d, n, m);while (m --) {int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}int t dijkstra();printf(%d, t);return 0;
}
3.Bellman-Ford算法存在负权边有边数限制最短路
有负权回路最短路不一定存在 for k 次 for 所有边 a, b, w 松弛操作dist[b] min(dist[b,dist[a]w) 给定一个 n 个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。 请你求出从 1号点到 n 号点的最多经过 k 条边的最短距离如果无法从 1 号点走到 n 号点输出 impossible。 注意图中可能 存在负权回路 。 #include cstdio
#include cstring
#include iostreamusing namespace std;int dist[505], backup[505];
int n, m, k;struct edge {int a, b, w;
} edges[10010];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 i 0; i m; i ) {int a edges[i].a, b edges[i].b, w edges[i].w;dist[b] min(dist[b], w backup[a]);}}}int main() {scanf(%d%d%d, n, m, k);for (int i 0; i m; i ) {int a, b, c;scanf(%d%d%d, a, b, c);edges[i] {a, b, c};}bellman_ford();if (dist[n] 0x3f3f3f3f / 2) puts(impossible);else printf(%d, dist[n]);return 0;
}4.SPFA算法与负权边无负权回路 给定一个 n个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。 请你求出 1号点到 n 号点的最短距离如果无法从 11 号点走到 n 号点则输出 impossible。 数据保证不存在负权回路。 #include iostream
#include cstring
#include queueusing namespace std;const int N 1e5 10;int idx, h[N], ne[N], e[N], w[N];int n, m;// 判断该点是否在队列
bool st[N];
int dist[N];void add(int a, int b, int c) {e[idx] b;ne[idx] h[a];w[idx] c;h[a] idx ;
}int spfa() {memset(dist, 0x3f, sizeof dist);dist[1] 0;queueint q;q.emplace(1);st[1] 1;while (!q.empty()) {int t q.front();q.pop();st[t] 0;for (int i h[t]; i ! -1; i ne[i]) {if (dist[e[i]] dist[t] w[i]) {dist[e[i]] dist[t] w[i];if (!st[e[i]]) {q.emplace(e[i]);st[e[i]] 1;}}}}return dist[n];
}int main() {ios::sync_with_stdio(false);memset(h, -1, sizeof h);cin n m;while (m--) {int a, b, c;cin a b c;add(a, b, c);}int t spfa();if (t 0x3f3f3f3f) cout impossible endl;else cout t;return 0;}5.Floyd求在求最短路多源 给定一个 n 个点 m条边的有向图图中可能存在重边和自环边权可能为负数。 再给定 k 个询问每个询问包含两个整数 x 和 y表示查询从点 x 到点 y 的最短距离如果路径不存在则输出 impossible。 数据保证图中不存在负权回路。 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 210, inf 1e9;int d[N][N];int 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() {int m, k;cin 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 a, b, c;cin a b c;d[a][b] min(d[a][b], c);}floyd();while (k--) {int a, b;cin a b;if (d[a][b] inf / 2) puts(impossible);else cout d[a][b]endl;}return 0;
}
