题目:(出差)
题目描述(13届 C&C++ B组E题)
解题思路:
-
问题分析
-
问题实质是一个带权图的最短路径问题,但路径的权重包含两个部分:
-
从当前城市到下一个城市的路程时间。
-
当前城市的离开时间。
-
-
需要计算从城市1到城市N的最短时间。
-
-
图的表示
-
用邻接矩阵表示图,将不存在的边初始化为无穷大。
-
-
路径规划
-
使用Dijkstra算法,从城市1开始,动态更新到其他城市的最短路径时间。
-
-
特殊处理
-
起点城市(城市1)的离开时间
staytime[0]
设为0,因为小明可以直接出发。
-
-
时间复杂度
-
Dijkstra的时间复杂度为 O(N2)O(N^2)O(N2) (由于使用邻接矩阵实现),在节点数较小时仍然可行。
-
代码实现(C语言):
#define maxn 1001
#define inf INT_MAX
#define edgetype int#include <stdio.h>
#include <stdlib.h>
#include <limits.h>void initedges(edgetype graph[maxn][maxn], int n)
{int i, j;for (i = 0; i < n; i++){for (j = 0; j < n; j++){graph[i][j] = inf;}}
}void addedges(edgetype graph[maxn][maxn], int u, int v, int w)
{if (graph[u][v] == inf || w < graph[u][v]){graph[u][v] = w;}if (graph[v][u] == inf || w < graph[v][u]){graph[v][u] = w;}
}void dijkstra(edgetype graph[maxn][maxn], int s, int n, edgetype dist[maxn], edgetype staytime[maxn])
{int visited[maxn];int i;for (i = 0; i < n; i++){dist[i] = inf;visited[i] = 0;}dist[s] = 0;while (1){int minindex = -1;int min = inf;for (int i = 0; i < n; i++){if (!visited[i] && dist[i] < min) {min = dist[i];minindex = i;}}if (min == inf){break;}visited[minindex] = 1;for (i = 0; i < n; i++){int u = graph[minindex][i];if (visited[i]){continue;}if (u == inf){continue;}if (dist[i] == inf || dist[i] > min + u + staytime[i]){dist[i] = min + u + staytime[i];}}}
}int main(int argc, char *argv[])
{int N, M, i, u, v, w;edgetype staytime[maxn], graph[maxn][maxn], dist[maxn];scanf("%d %d", &N, &M);for (i = 0; i < N; i++){scanf("%d", &staytime[i]);}staytime[0] = 0;initedges(graph, N);for (i = 0; i < M; i++){scanf("%d %d %d", &u, &v, &w);addedges(graph, u - 1, v - 1, w);}dijkstra(graph, 0, N, dist, staytime);printf("%d", dist[N - 1] - staytime[N - 1]);return 0;
}
得到运行结果:
代码分析:
-
图的初始化
-
initedges
函数将图中所有的边权值初始化为无穷大(inf
),表示没有直接连通的路径。
-
-
添加边
-
addedges
函数会将边(u, v)
及其权值w
加入到邻接矩阵中,同时判断是否已有更短路径,如果有就更新。
-
-
Dijkstra算法
-
核心部分是
dijkstra
函数:-
使用一个
visited
数组标记已确定最短路径的节点。 -
每次找到当前未访问节点中距离起点最近的节点。
-
松弛操作:尝试更新所有相邻节点的最短距离,考虑路径花费和目标节点的离开时间。
-
-
-
输入输出
-
输入部分:城市数量
N
、道路数量M
、每个城市离开时间以及M
条双向边信息。 -
输出部分:从起点城市
1
到终点城市N
的最短时间。
-
-
重要逻辑
-
在
dijkstra
中更新距离时,将离开时间加入权值计算:dist[i] = min + u + staytime[i]
。
-
难度分析
⭐️⭐️⭐️⭐️⭐️难难难难难急急急急急急急
总结
本代码解决了一个加权图中的特殊最短路径问题,考虑到离开时间的影响。
它适用于小型的城市网络,提供了可靠的解法。