文章
99
粉丝
101
获赞
8
访问
23.2k
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 1e2 + 5;
constexpr int mmod = 1e5;
int father[maxn];
int graph[maxn][maxn];
int n, m;
int find(int x) {
if (father[x] == x)
return x;
else {
father[x] = find(father[x]);
return father[x];
}
}
/*
两个推断:
(1)在添加第k条路径时,如果路径k连接的两个城市A 、B已经通过其他路径间接的连通了,那么第k条路径
绝对不是AB间的最短路径(第k条路径之后的路径也不可能有比当前AB路径更短的路径了,因为第k条路
径的长度会大于前k-1条路径的总和)
(2)在添加第k条路径时,如果路径k连接的两个城市A 、B是第一次被连通了(也就是说此前没有任何路径能连通AB,
包括通过多条路径间接连通),那么路径k就是AB之间的最短距离了,因为以后不可能存在更短的路径连接AB,
以后的单条路径只会越来越长。
通过上述的推断,我们可以利通过建立一个最小连通树的同时算出0号城市到各个城市的最小路径。
登录后发布评论
暂无评论,来抢沙发