Dijkstra算法可以解決最短路問題，針對單源有向圖，屬于貪心算法的一種，要求權值非負。
算法實現步驟： 初始化：起點dist[s]=0 其他dist[i]=INF 節點集合V[i]=0 注：C++中初始化最大值，如果設置為FFFFFFFF其實有問題，就像在這個問題中，如果將最大值加一，則出現了負數，所以#define INF 0x3f3f3f3f
初始化：起點dist[s]=0 其他dist[i]=INF 節點集合V[i]=0*注：C++中初始化最大值，如果設置為FFFFFFFF其實有問題，就像在這個問題中，如果將最大值加一，則出現了負數，所以#define INF 0x3f3f3f3f*循環n次，找到不屬于V的k且dist[k]最小的節點，V[k]=1對于不屬于V的i，更新：dist[i] = min(dist[i], dist[k] + weight[k][i]);那么我們來解決PAT上1003. Emergency (25)這個問題，題目如下：
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.InputEach input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) - the number of cities (and the cities are numbered from 0 to N-1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.OutputFor each test case, PRint in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.Sample Input5 6 0 21 2 1 5 30 1 10 2 20 3 11 2 12 4 13 4 1Sample Output2 4作為最短路的變形題目，我們要注意對于maxTeam和countShst的記錄： 如果s-k-i路線最短，那么i的最短路個數就等于k的最短路個數，且i的maxTeam就等于k的maxTeam帶上自己的人數。 如果說s-k-i長度與s-i相等，那么最短路個數等于k的最短路個數加上i的最短路個數，這個時候需要判斷下走哪條路maxTeam比較大。
代碼實現：
#include <iostream>#include <stdio.h>#include <limits.h>#include <algorithm>using namespace std;#define INF 0x3F3F3F3F;int N, M, S, E, C1, C2;int teams[502] = { 0 };int weight[502][502] = { 0 };int dist[502];bool mark[502] = { false };int countShst[502];int maxTeam[502] = { 0 };void dijkstra();int main(void){ cin >> N; cin >> M >> S >> E; //memset(dist, INF, sizeof(dist)); //memset(mark, 0, sizeof(mark)); //memset(countShst, 1, sizeof(countShst)); for (int i = 0; i < 502; i++){ dist[i] = INF; mark[i] = 0; maxTeam[i] = 0; countShst[i] = 0; for (int j = 0; j < 502; j++) weight[i][j] = weight[j][i] = INF; } for (int i = 0; i < N; i++) { cin >> teams[i]; maxTeam[i] = teams[i]; } for (int i = 0; i < M; i++) { cin >> C1 >> C2; cin >> weight[C1][C2]; weight[C2][C1] = weight[C1][C2]; //cout << "weight" << weight[C2][C1]; } dist[S] = 0; dijkstra(); //cout << "shortest: " << dist[E] << " MaxTeams: " << maxTeam[E]<<" "<<teams[S]; cout << countShst[E] << " " << maxTeam[E] << endl; system("pause"); return 0;}void dijkstra(){ int k = S, dmin; //mark[k] = true; //int flag = 0; countShst[S] = 1; for (int i = 0; i < N; i++) { //int k = -1; //dist[S] = INF; dmin = INF; for (int j = 0; j < N; j++) { if (!mark[j] && dist[j]<dmin) { dmin = dist[j]; k = j; } } //update mark[k] = true; for (int i = 0; i < N; i++) { if (!mark[i]) { if (weight[k][i] != 0 && dist[i] > dist[k] + weight[k][i]) { maxTeam[i] = maxTeam[k] + teams[i]; countShst[i] = countShst[k]; } else if (weight[k][i] != 0 && dist[i] == dist[k] + weight[k][i]) { countShst[i] += countShst[k]; if (maxTeam[i] < maxTeam[k] + teams[i]) maxTeam[i] = maxTeam[k] + teams[i]; } dist[i] = min(dist[i], dist[k] + weight[k][i]); } } }}新聞熱點
疑難解答
