蓝桥杯每日真题

蓝桥杯每日真题 - 第18天

题目：（出差）

题目描述（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]。