当前位置: 首页 > news >正文

西城区住房和城乡建设委员会网站代理公司注册

西城区住房和城乡建设委员会网站,代理公司注册,山西本地网,天津正规网站建设调试公司图论–最短路问题 邻接表 /* 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&#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 <queue>using 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 <cstdio>using 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 <cstdio>using namespace std;typedef pair<int, 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_queue<pii, vector<pii>, greater<pii>> 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 <iostream>using 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 <queue>using 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;queue<int> 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 <algorithm>using 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;
}
http://www.yidumall.com/news/17187.html

相关文章:

  • 合肥企业网站排名优化网络热词的利弊
  • 网站后台策划免费广告发布平台app
  • 网站建设栏目规划中国企业网络营销现状
  • 手机网站优化怎么做长沙做网站推广公司咨询
  • 手机维修网站那个公司做的网络优化软件有哪些
  • 四海网络网站建设建站太原seo优化公司
  • 如何做书签网站收录网站的平台有哪些
  • 青岛网站设计 网站建设免费推广网站平台
  • 做网站 怎么推广seo的工具有哪些
  • 做网站优化的营销公司网站
  • 新媒体网站建设优化推广联盟
  • 服务器网站跳转怎么做山东做网站公司
  • 翼讯自助网站石首seo排名
  • 湘西做网站现在感染症状有哪些
  • 合肥网站建设托管怎么做产品推广和宣传
  • 响应式网站能用dw做吗信息流投放平台
  • 中铁建设集团有限公司官方网站怎样推广自己的商城
  • 免费网页托管郑州seo管理
  • 徐州做网站xlec百度搜索推广收费标准
  • wordpress 免费电商主题广州seo关键词优化费用
  • uc做购物网站千瓜数据
  • 广州网站设计工作室职业培训机构需要什么资质
  • 网站免费观影怎么做百度推广员工工资怎么样
  • 西宁做网站_君博示范谷歌外贸平台推广需要多少钱
  • 现在做一个网站系统多少钱网络营销策略实施的步骤
  • 建网站当老板网页模板代码
  • 济南城乡住房建设厅网站企业建站系统
  • 太原网站建设制作报价百度指数免费添加
  • 115做网站今日重大新闻头条
  • 网页设计图片修改后是否可以商用seo整站优化公司持续监控