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

蓝桥杯每日真题 - 第18天

news 2025/7/8 21:38:51

题目：（出差）

题目描述（13届 C&C++ B组E题）

解题思路：

问题分析
- 问题实质是一个带权图的最短路径问题，但路径的权重包含两个部分：
  1. 从当前城市到下一个城市的路程时间。
  2. 当前城市的离开时间。
- 需要计算从城市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]。