-
743. 网络延迟时间 - 力扣（LeetCode）
法一：单源最短路径——Bellman-Ford
O(NM)
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
dist = vector<int>(n + 1, 1e9);
dist[k] = 0;
for (int round = 1; round < n; round++) {
bool flag = true;
for (vector<int>& edge : times) {
int x = edge[0];
int y = edge[1];
int z = edge[2];
if (dist[x] + z < dist[y]) {
dist[y] = dist[x] + z;
flag = false;
}
}
if (flag) break;
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dist[i]);
return ans == 1e9 ? -1 : ans;
}
private:
vector<int> dist;
};
法二.1：单源最短路径——Dijkstra
O(NN)
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
ver = vector<vector<int>>(n + 1, vector<int>());
edge = vector<vector<int>>(n + 1, vector<int>());
for (vector<int>& time : times) {
int x = time[0];
int y = time[1];
int z = time[2];
ver[x].push_back(y);
edge[x].push_back(z);
}
dist = vector<int>(n + 1, 1e9);
dist[k] = 0;
expand = vector<bool>(n + 1, false);
for (int round = 1; round <= n; round++) {
int minVal = 1e9, minIdx = 0;
for (int i = 1; i <= n; i++) {
if (!expand[i] && dist[i] < minVal) {
minVal = dist[i];
minIdx = i;
}
}
if (minIdx == 0) break;
expand[minIdx] = true;
for (int i = 0; i < ver[minIdx].size(); i++) {
int y = ver[minIdx][i];
int z = edge[minIdx][i];
if (dist[y] > dist[minIdx] + z) {
dist[y] = dist[minIdx] + z;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dist[i]);
return ans == 1e9 ? -1 : ans;
}
private:
vector<int> dist;
// 出边数组
vector<vector<int>> ver;
// 每条边的权重
vector<vector<int>> edge;
// 记录每个点是否已被扩展
vector<bool> expand;
};
法二.2：单源最短路径——Dijkstra+堆
O(MlogM) 此题堆用了懒惰删除，所以为logM
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
ver = vector<vector<int>>(n + 1, vector<int>());
edge = vector<vector<int>>(n + 1, vector<int>());
for (vector<int>& time : times) {
int x = time[0];
int y = time[1];
int z = time[2];
ver[x].push_back(y);
edge[x].push_back(z);
}
dist = vector<int>(n + 1, 1e9);
dist[k] = 0;
expand = vector<bool>(n + 1, false);
q.push({0, k});
while (!q.empty()) {
int minIdx = q.top().second;
q.pop();
if (expand[minIdx]) continue; // 懒惰删除
expand[minIdx] = true;
for (int i = 0; i < ver[minIdx].size(); i++) {
int y = ver[minIdx][i];
int z = edge[minIdx][i];
if (dist[y] > dist[minIdx] + z) {
dist[y] = dist[minIdx] + z;
q.push({-dist[y], y}); // 此处只要更新就入堆，在出堆时再判断是否已扩展——懒惰删除
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dist[i]);
return ans == 1e9 ? -1 : ans;
}
private:
vector<int> dist;
// 出边数组
vector<vector<int>> ver;
// 每条边的权重
vector<vector<int>> edge;
// 记录每个点是否已被扩展
vector<bool> expand;
// <-距离，编号>
priority_queue<pair<int, int>> q;
};
-
1334. 阈值距离内邻居最少的城市 - 力扣（LeetCode）
多元最短路径——Floyd
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
// 邻接矩阵
vector<vector<int>> d(n, vector<int>(n, 1e9));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (vector<int>& edge : edges) {
int x = edge[0];
int y = edge[1];
int z = edge[2];
d[x][y] = d[y][x] = z;
}
// Floyd
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
// 解题
int minNeighbor = 1e9, ans;
for (int i = 0; i < n; i++) {
int neighbor = 0;
for (int j = 0; j < n; j++)
if (i != j && d[i][j] <= distanceThreshold)
neighbor++;
if (neighbor < minNeighbor || neighbor == minNeighbor && i > ans) {
minNeighbor = neighbor;
ans = i;
}
}
return ans;
}
};
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
// 建边
vector<vector<int>> edges;
int n = points.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
edges.push_back({i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])});
// Kruskal
sort(edges.begin(), edges.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
int ans = 0;
// 并查集
fa = vector<int>(n);
for (int i = 0; i < n; i++) fa[i] = i;
for (vector<int> edge : edges) {
int x = edge[0];
int y = edge[1];
int z = edge[2];
x = find(x);
y = find(y);
if (x != y) {
ans += z;
fa[x] = y;
}
}
return ans;
}
private:
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
vector<int> fa;
};
class Solution {
public:
int myAtoi(string s) {
int index = 0, n = s.length();
// 1. 空格
while (index < n && s[index] == ' ') index++;
// 2. 符号
int sign = 1;
if (index < n && (s[index] == '+' || s[index] == '-')) {
sign = s[index] == '+' ? 1 : -1;
index++;
}
// 3. 转换
while (index < n && s[index] == '0') index++;
int val = 0;
while (index < n && s[index] >= '0' && s[index] <= '9') {
// 4. 舍入
if (val > (2147483647 - (s[index] - '0')) / 10)
if (sign == 1) return 2147483647;
else return -2147483648;
val = val * 10 + (s[index] - '0');
index++;
}
return sign * val;
}
};
