网站建设可以一次性进损益吗,网站模糊背景,wordpress页面连接数据库,合肥网站建设毅耘题目#xff1a;#xff08;出差#xff09;
题目描述#xff08;13届 CC B组E题#xff09; 解题思路#xff1a; 问题分析 问题实质是一个带权图的最短路径问题#xff0c;但路径的权重包含两个部分#xff1a; 从当前城市到下一个城市的路程时间。 当前城市的…题目出差
题目描述13届 CC 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.hvoid 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]。 难度分析
⭐️⭐️⭐️⭐️⭐️难难难难难急急急急急急急 总结
本代码解决了一个加权图中的特殊最短路径问题考虑到离开时间的影响。 它适用于小型的城市网络提供了可靠的解法。
