立志用最少的代碼做最高效的表達(dá)

---

PAT甲級(jí)最優(yōu)題解——>傳送門(mén)

---

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.

Input Specification:
Each 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,c2and 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 C1toC2

Output Specification:
For 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 Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output:
2 4

---

題目分析

題意：
n個(gè)城市，每個(gè)城市都有救火隊(duì)，城市間道路雙向連通，要求輸出a城-b城最短路徑的數(shù)目，同時(shí)這些路徑中最多救火隊(duì)的數(shù)量

注意：
1、城市間道路雙向連通
2、輸出的不是最短路徑長(zhǎng)度，是最短路徑數(shù)目（哭，卡了我半個(gè)小時(shí)）

分析：
本質(zhì)為求最短路徑問(wèn)題。

一般來(lái)講，求最短路有迪杰斯特拉和DFS兩種算法。個(gè)人比較推薦DFS，碼量小，思路更簡(jiǎn)潔。

---

DFS版代碼

#include<bits/stdc++.h> using namespace std;const int MAX_LEN = 0x3f3f3f3f; const int c_maxn = 500+10; int G[c_maxn][c_maxn]; //城市地圖 int c_pro[c_maxn]; //每個(gè)城市的救火隊(duì)數(shù)量 int vis[c_maxn]; //-1為有回路、0為正在訪問(wèn)、1為已訪問(wèn) int c_n, r_n, sta, fin; //城市數(shù)量，道路數(shù)量，起點(diǎn)、終點(diǎn) int Min=MAX_LEN, Max = -1, num_r = 0; //最優(yōu)路程和救火隊(duì)數(shù)量 void dfs(int u, int len, int value) {if(len > Min) return; //剪枝 if(u == fin) {if(Min > len) { //如果路程更短，則直接更新 Min = len; Max = value;num_r = 1;} else if(Min == len) { //如果路程相等，則比較救火隊(duì)數(shù)量 Max = max(value, Max);num_r++;}return;}for(int v = 0; v < c_n; v++) {if(G[u][v] != -1) {if(vis[v] == 1) continue;vis[v] = 1;dfs(v, len+G[u][v], value+c_pro[v]);vis[v] = 0;} // cout << u << ' ' << v << ' ' << G[u][v] << '\n';} }int main() {memset(G, -1, sizeof(G));cin >> c_n >> r_n >> sta >> fin;for(int i = 0; i < c_n; i++) cin >> c_pro[i];for(int i = 0; i < r_n; i++) {int x1, x2, v;cin >> x1 >> x2 >> v;G[x1][x2] = G[x2][x1] = v;}vis[sta] = 1;dfs(sta, 0, c_pro[sta]); //起始節(jié)點(diǎn)、道路長(zhǎng)度、起始救火隊(duì)數(shù)量 cout << num_r << ' ' << Max << '\n';return 0; } 超強(qiáng)干貨來(lái)襲 云風(fēng)專(zhuān)訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的1003 Emergency (25 分)【Dijastra与DFS解法】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。