解题思路
这是一个带有天气限制的最短路径问题。需要特别考虑恶劣天气对航行时间的影响。
关键点：
- 航行过程中不能遇到恶劣天气
- 如果遇到恶劣天气需要等待结束
- 实际距离需要考虑等待时间
- 到达时间需要加1天
算法步骤：
- 初始化距离矩阵和天气限制
- 从起点开始更新所有可达点
- 选择最近的未访问点
- 更新经过该点的路径
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
const int INF = 1001;
// 检查航行时间是否与恶劣天气重叠
bool isAllowed(int start1, int end1, int start2, int end2) {
return end1 < start2 || end2 < start1;
}
public:
int shortestPath(int n, int m, vector<vector<int>>& edges) {
// 初始化距离矩阵和天气限制
vector<vector<int>> dist_matrix(n + 1, vector<int>(n + 1, INF));
vector<vector<pair<int, int>>> weather(n + 1, vector<pair<int, int>>(n + 1));
// 构建图
for (const auto& edge : edges) {
int u = edge[0], v = edge[1], k = edge[2];
int x = edge[3], y = edge[4];
dist_matrix[u][v] = dist_matrix[v][u] = k;
weather[u][v] = weather[v][u] = {x, y};
}
// Dijkstra算法
vector<int> dist(n + 1, INF);
vector<bool> visited(n + 1, false);
dist[1] = 1;
visited[1] = true;
// 初始化与起点直接相连的点
for (int i = 2; i <= n; i++) {
if (dist_matrix[1][i] != INF) {
if (!isAllowed(dist[1], dist[1] + dist_matrix[1][i] - 1,
weather[1][i].first, weather[1][i].second)) {
dist[i] = weather[1][i].second + dist_matrix[1][i] + 1;
} else {
dist[i] = dist[1] + dist_matrix[1][i];
}
}
}
// 主循环
for (int i = 2; i <= n; i++) {
// 找到最近的未访问点
int min_dist = INF;
int u = 0;
for (int j = 2; j <= n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
u = j;
}
}
visited[u] = true;
// 更新通过u可达的点
for (int v = 2; v <= n; v++) {
if (!visited[v] && dist_matrix[u][v] != INF) {
int new_dist = dist[u] + dist_matrix[u][v];
if (!isAllowed(dist[u], dist[u] + dist_matrix[u][v] - 1,
weather[u][v].first, weather[u][v].second)) {
new_dist = weather[u][v].second + dist_matrix[u][v] + 1;
}
dist[v] = min(dist[v], new_dist);
}
}
}
return dist[n];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> edges(m, vector<int>(5));
for (int i = 0; i < m; i++) {
for (int j = 0; j < 5; j++) {
cin >> edges[i][j];
}
}
Solution solution;
cout << solution.shortestPath(n, m, edges) << endl;
return 0;
}
import java.util.*;
class Solution {
private static final int INF = 1001;
// 检查航行时间是否与恶劣天气重叠
private boolean isAllowed(int start1, int end1, int start2, int end2) {
return end1 < start2 || end2 < start1;
}
public int shortestPath(int n, int m, int[][] edges) {
// 初始化距离矩阵和天气限制
int[][] distMatrix = new int[n + 1][n + 1];
int[][][] weather = new int[n + 1][n + 1][2];
for (int i = 0; i <= n; i++) {
Arrays.fill(distMatrix[i], INF);
}
// 构建图
for (int[] edge : edges) {
int u = edge[0], v = edge[1], k = edge[2];
int x = edge[3], y = edge[4];
distMatrix[u][v] = distMatrix[v][u] = k;
weather[u][v][0] = weather[v][u][0] = x;
weather[u][v][1] = weather[v][u][1] = y;
}
// Dijkstra算法
int[] dist = new int[n + 1];
boolean[] visited = new boolean[n + 1];
Arrays.fill(dist, INF);
dist[1] = 1;
visited[1] = true;
// 初始化与起点直接相连的点
for (int i = 2; i <= n; i++) {
if (distMatrix[1][i] != INF) {
if (!isAllowed(dist[1], dist[1] + distMatrix[1][i] - 1,
weather[1][i][0], weather[1][i][1])) {
dist[i] = weather[1][i][1] + distMatrix[1][i] + 1;
} else {
dist[i] = dist[1] + distMatrix[1][i];
}
}
}
// 主循环
for (int i = 2; i <= n; i++) {
// 找到最近的未访问点
int minDist = INF;
int u = 0;
for (int j = 2; j <= n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
visited[u] = true;
// 更新通过u可达的点
for (int v = 2; v <= n; v++) {
if (!visited[v] && distMatrix[u][v] != INF) {
int newDist = dist[u] + distMatrix[u][v];
if (!isAllowed(dist[u], dist[u] + distMatrix[u][v] - 1,
weather[u][v][0], weather[u][v][1])) {
newDist = weather[u][v][1] + distMatrix[u][v] + 1;
}
dist[v] = Math.min(dist[v], newDist);
}
}
}
return dist[n];
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] edges = new int[m][5];
for (int i = 0; i < m; i++) {
for (int j = 0; j < 5; j++) {
edges[i][j] = sc.nextInt();
}
}
Solution solution = new Solution();
System.out.println(solution.shortestPath(n, m, edges));
sc.close();
}
}
class Solution:
def __init__(self):
self.INF = 1001
def is_allowed(self, start1: int, end1: int, start2: int, end2: int) -> bool:
"""检查航行时间是否与恶劣天气重叠"""
return end1 < start2 or end2 < start1
def shortest_path(self, n: int, m: int, edges: list) -> int:
# 初始化距离矩阵和天气限制
dist_matrix = [[self.INF] * (n + 1) for _ in range(n + 1)]
weather = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]
# 构建图
for edge in edges:
u, v, k, x, y = edge
dist_matrix[u][v] = dist_matrix[v][u] = k
weather[u][v] = weather[v][u] = [x, y]
# Dijkstra算法
dist = [self.INF] * (n + 1)
visited = [False] * (n + 1)
dist[1] = 1
visited[1] = True
# 初始化与起点直接相连的点
for i in range(2, n + 1):
if dist_matrix[1][i] != self.INF:
if not self.is_allowed(dist[1], dist[1] + dist_matrix[1][i] - 1,
weather[1][i][0], weather[1][i][1]):
dist[i] = weather[1][i][1] + dist_matrix[1][i] + 1
else:
dist[i] = dist[1] + dist_matrix[1][i]
# 主循环
for _ in range(2, n + 1):
# 找到最近的未访问点
min_dist = self.INF
u = 0
for j in range(2, n + 1):
if not visited[j] and dist[j] < min_dist:
min_dist = dist[j]
u = j
visited[u] = True
# 更新通过u可达的点
for v in range(2, n + 1):
if not visited[v] and dist_matrix[u][v] != self.INF:
new_dist = dist[u] + dist_matrix[u][v]
if not self.is_allowed(dist[u], dist[u] + dist_matrix[u][v] - 1,
weather[u][v][0], weather[u][v][1]):
new_dist = weather[u][v][1] + dist_matrix[u][v] + 1
dist[v] = min(dist[v], new_dist)
return dist[n]
def main():
n, m = map(int, input().split())
edges = []
for _ in range(m):
edges.append(list(map(int, input().split())))
solution = Solution()
print(solution.shortest_path(n, m, edges))
if __name__ == "__main__":
main()
算法及复杂度
- 算法：改进的
最短路径算法
- 时间复杂度：
，其中
是顶点数
- 空间复杂度：
京公网安备 11010502036488号