给网站网站做优化,钦州电商网站建设,永久免费的网站,腾讯和中国联通C : 追星 文章目录 C : 追星DescriptionInputOutputSampleInputOutput 解题思路AC代码#xff1a; Description
城市总共有N座。yintama是右京女神的狂热粉#xff0c;当他得知右京女神将要在城市N举办演唱会的时候#xff0c;马上开始准备动身前往城市N。原本他可以直接乘…C : 追星 文章目录 C : 追星DescriptionInputOutputSampleInputOutput 解题思路AC代码 Description
城市总共有N座。yintama是右京女神的狂热粉当他得知右京女神将要在城市N举办演唱会的时候马上开始准备动身前往城市N。原本他可以直接乘飞机直达城市N然而贫穷使他屈服他必须选择总花费最少的那条路径。 设总共有N座城市(2N1000城市编号分别为1,2,3……N。M条航线(1M2000)每条航线连接两座城市相互可以到达无向的。 yintama目前在身在城市1求最后yintama参加右京女神演唱会所需要的最少花费。PS重边考虑一下
Input
有多组输入。 第一行输入一个N、M代表城市的总数以及航线的总数。 接下来M行每行输入三个数字u v w代表城市u、v之间存在航线机票花费为w。
Output
每行输出一个数代表yintama参加右京女神演唱会所需的最少花费。
Sample
Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100Output
90解题思路
这道题目是一个图论的单源最短路径可以通过Dijkstra算法来求解。关键在于找到从起始城市城市1到目的城市城市N的最短路径这道题是指钱。 理解问题 有N个城市和M条航线。每条航线连接两个城市并有一个与之相关的机票花费权重。需要从城市1出发到达城市N使得总花费最小。 数据结构选择 使用一个二维数组来表示城市之间的航线和对应的花费。数组的大小为N×N其中graph[i][j]表示从城市i到城市j的机票花费。 处理重边 如果有多条航线连接同一对城市只保留花费最小的那条。这意味着在读取输入时需要更新二维数组中的值只保留最小的花费。 使用Dijkstra算法 【数据结构】B : DS图应用–最短路径 输出结果 最终距离数组中的distance[N-1]因为数组是从0开始计数的就是从城市1到城市N的最小花费。 注意点无向图处理重边可以不使用last数组记录上节点
AC代码
#includeiostream
#includeclimits
using namespace std;// 我会写两份代码
void Dijkstra(int** graph, int n) {int* distance new int[n];bool* fixed new bool[n];// 预处理for (int i 0; i n; i) {distance[i] INT_MAX;fixed[i] false;}distance[0] 0;for (int count 0; count n - 1; count) {int min INT_MAX, min_index;// 找最小目前最短的及其下标for (int v 0; v n; v)if (!fixed[v] distance[v] min)min distance[v], min_index v;fixed[min_index] true;for (int v 0; v n; v)if (!fixed[v] graph[min_index][v] distance[min_index] ! INT_MAX distance[min_index] graph[min_index][v] distance[v])distance[v] distance[min_index] graph[min_index][v];}cout distance[n - 1] endl;delete[] distance;delete[] fixed;
}int main() {int n, m;cin n m;int** graph new int* [n];for (int i 0; i n; i)graph[i] new int[n];for (int i 0; i n; i)for (int j 0; j n; j)graph[i][j] 0;for (int i 0; i m; i) {int a, b, c;cin a b c;if (graph[a - 1][b - 1] 0 || c graph[a - 1][b - 1]) {graph[a - 1][b - 1] c;graph[b - 1][a - 1] c;}}Dijkstra(graph, n);for (int i 0; i n; i)delete[] graph[i];delete[] graph;
}
