PTA 1003 Emergency-有解無憂

題目翻譯

作為一個城市的緊急救助隊的隊長的你有一份特殊的你所在國家的地圖，地圖展示了一些通過道路連接的分散的城市，每一個城市都有急救隊并且地圖上標出了一些城市之間道路的長度，當你接到一個從其他城市打來的電話時，你的任務是帶領你的隊員盡快到達那里同時叫上盡可能多的幫手，

輸入格式

每一個輸入檔案包含一個測驗樣例，對于每一個測驗樣例，第一行有4個正整數：N(≤500)-城市的數量（城市編號從0到N-1)，M-道路的數量，C₁和C₂-分別為你現在所在的城市和你必須要去救援的城市，下一行包含N個整數--分別是第i個城市所擁有的救援隊的數量，接下來的M行分別用三個整數C₁和C₂和L表示一對城市和他們之間道路的長度，C₁ 和C₂之間保證至少有一條通路，

輸出格式

對于每一個測驗樣例，輸出兩個數字在一行：C₁和C₂之間的最短路徑的條數以及你最多可以集合的救援隊的數量，一行中的所有數字都必須用一個空格隔開并且行尾沒有多余的空格，

把自己的一些想法和《演算法筆記》里對Dijstra的介紹結合了一下（其實主要是演算法筆記里的內容orz），希望能幫助大家理解這道題吧，小白第一次寫博客，如果有錯誤請大家指出，感謝，

題目分析：

讀完題目后，我們可以確定這是一個單源最短路的問題，即求解從C₁到C₂的最短路徑，如果有多個的話就輸出路徑的個數，并且求出這些路徑中能夠集結的救援隊個數最多的路，對于非負權的單源最短路問題，我們一般用Dijstra演算法解決，

Dijstra演算法基本策略：

設定集合S存放已被訪問的定點（即已訪問過的城市），然后執行n次下面的兩個步驟（n為頂點個數）：

每次從集合V-S（即未訪問過的城市）中選擇與起點s的最短距離最小的一個頂點（記為u），訪問并加入集合S（即標記為已訪問），
之后，以頂點u為中介，優化與u連通的其他城市嗎，如果借助頂點u能夠使他們到達起點s的距離更短的話，就更新他們與s之間的最短距離，
重復回到1

具體實作時的一些細節

涉及到圖的問題我們一般用鄰接矩陣或者鄰接表來存盤圖，這道題的城市，也就是節點，的個數最多是510，在我們接受范圍以內，所以我推薦用鄰接矩陣來存盤圖，這樣在撰寫代碼時相較于鄰接表會方便一點，
在實作Dijstra演算法時，我們一般用一個bool型別的一維陣列來標記各個頂點是否被訪問，我們暫且用vis來命名這個陣列，一開始，我們先令vis[s]=true，也就是先把起點標記為已訪問，之后每訪問一個節點，都把它標記為true，
我們一般用一個int型的陣列來存放各個頂點到起點的最短距離，我們一開始先把這個陣列中除了起點以外都初始化為一個很大的數字，可以是或者是0xfffffff，但最好不要使用0x7fffffff，防止兩個數相加發生溢位，

核心演算法偽代碼實作

 1 void Dijstra(G, d[], s)
 2 {
 3     初始化
 4         for (回圈n次) {
 5             u = 使d[u]最小的還未被訪問的頂點的標號;
 6             標記u為已訪問
 7                 for (從u出發能到達的所有頂點v) {
 8                     if (v未被訪問 && 以u為中介點使s到頂點v的最短距離d[v]更優) {
 9                         優化d[v]；
10                     }
11             }
12     }
13 
14 }

完整代碼

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 const int MAXV = 510;
 5 const int INF = 100000000;
 6 
 7 int n, m, s, ed, G[MAXV][MAXV], weight[MAXV];
 8 int d[MAXV], w[MAXV], num[MAXV];
 9 bool vis[MAXV];
10 
11 void Dijkstra();
12 
13 int main()
14 {
15     scanf("%d%d%d%d", &n, &m, &s, &ed);
16 
17     for (int i = 0; i < n; i++)
18         scanf("%d", &weight[i]);
19 
20     fill(G[0], G[0] + MAXV * MAXV, INF);
21     for (int i = 0; i < m; i++)
22     {
23         int u, v;
24         scanf("%d%d", &u, &v);
25         scanf("%d", &G[u][v]);
26         G[v][u] = G[u][v];
27     }
28 
29     Dijkstra();
30 
31     printf("%d %d", num[ed], w[ed]);
32     return 0;
33 }
34 
35 void Dijkstra()
36 {
37     fill(d, d + MAXV, INF);
38     fill(num, num + MAXV, 0);
39     fill(w, w + MAXV, 0);
40     fill(vis, vis + MAXV, false);
41     d[s] = 0;
42     w[s] = weight[s];
43     num[s] = 1;
44 
45     for (int i = 0; i < n; i++)
46     {
47         int u = -1, MIN = INF;
48         for (int j = 0; j < n; j++)
49             if (!vis[j] && d[j] < MIN)
50             {
51                 u = j;
52                 MIN = d[j];
53             }
54         if (u == -1)
55             return;
56         vis[u] = true;
57 
58         for (int j = 0; j < n; j++)
59             if (G[u][j] != INF && !vis[j])
60                 if (d[j] > G[u][j] + d[u])
61                 {
62                     d[j] = G[u][j] + d[u];
63                     w[j] = w[u] + weight[j];
64                     num[j] = num[u];
65                 }
66                 else if (d[j] == G[u][j] + d[u])
67                 {
68                     w[j] = max(w[j], w[u] + weight[j]);
69                     num[j] += num[u];
70                 }
71     }
72 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198919.html

標籤：其他

上一篇：資料結構（C語言版）---線性表順序存盤表示

下一篇：線索二叉樹（C語言描述）