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;
}