题目：（出差）

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

难度分析

⭐️⭐️⭐️⭐️⭐️难难难难难急急急急急急急

总结

本代码解决了一个加权图中的特殊最短路径问题，考虑到离开时间的影响。
它适用于小型的城市网络，提供了可靠的解法。