【数据结构】C : 追星

C : 追星

Description

城市总共有N座。yintama是右京女神的狂热粉，当他得知右京女神将要在城市N举办演唱会的时候，马上开始准备动身前往城市N。原本他可以直接乘飞机直达城市N，然而贫穷使他屈服，他必须选择总花费最少的那条路径。
设总共有N座城市(2<=N<=1000），城市编号分别为1,2,3……N。M条航线(1<=M<=2000)，每条航线连接两座城市，相互可以到达（无向的）。
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 100

Output

90

解题思路

这道题目是一个图论的单源最短路径，可以通过Dijkstra算法来求解。关键在于找到从起始城市（城市1）到目的城市（城市N）的最短路径（这道题是指钱）。

1. 理解问题：

   • 有N个城市和M条航线。
   • 每条航线连接两个城市，并有一个与之相关的机票花费（权重）。
   • 需要从城市1出发，到达城市N，使得总花费最小。

2. 数据结构选择：

   • 使用一个二维数组来表示城市之间的航线和对应的花费。数组的大小为N×N，其中graph[i][j]表示从城市i到城市j的机票花费。

3. 处理重边：

   • 如果有多条航线连接同一对城市，只保留花费最小的那条。这意味着在读取输入时，需要更新二维数组中的值，只保留最小的花费。

4. 使用Dijkstra算法：

   【数据结构】B : DS图应用–最短路径

5. 输出结果：

   • 最终距离数组中的distance[N-1]（因为数组是从0开始计数的）就是从城市1到城市N的最小花费。

6. 注意点：无向图，处理重边，可以不使用last数组记录上节点

AC代码：

#include<iostream>
#include<climits>
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;
}