【PAT算法之路】 – 專欄總攬
最短路徑幾乎是PAT出現頻率最高的題型之一，一般都需要70-100行代碼（C++），但是不用慌，因為這個代碼有40行以上都是靠背下來的（都是套路）。
我個人記的是
Dijkstra+DFS
，這種方法感覺比較通用，而且容易記住。
我們用一個例子來看看吧，就比如：
1030 Travel Plan (30 分)
1030 Travel Plan (30 分)
A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N−1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:
City1 City2 Distance Cost
where the numbers are all integers no more than 500, and are separated by a space.
Output Specification:
For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.
Sample Input:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output:
0 2 3 3 40
題目意思很簡單就是從一個指定的點出發，到指定的終點，求最短路徑，如果最短路徑不止一條，選擇Cost最小的那一條。
容我先給出代碼：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 99999999
int e[510][510];
int e2[510][510];
int dis[510];
bool vis[510];
vector<int> pre[510];
int n,m,s,d;
int min_cost = INF;
vector<int> path;
void dfs(int c,vector<int> temp_path){
temp_path.push_back(c);
if(c == s){
int sum_cost = 0;
for(int i=1;i<temp_path.size();i++)
sum_cost += e2[temp_path[i]][temp_path[i-1]];
if(min_cost > sum_cost){
min_cost = sum_cost;
path = temp_path;
}
return;
}
int len = pre[c].size();
for(int i=0;i<len;i++){
dfs(pre[c][i],temp_path);
}
temp_path.pop_back();
}
int main() {
fill(e[0],e[0]+510*510,INF);
fill(e2[0],e2[0]+510*510,INF);
fill(dis,dis+510,INF);
cin >> n >> m >> s >> d;
for(int i=0;i<m;i++){
int c1,c2,diss,cost;
cin >> c1 >> c2 >> diss >> cost;
e[c1][c2] = diss;
e[c2][c1] = diss;
e2[c1][c2] = cost;
e2[c2][c1] = cost;
}
dis[s] = 0;
for(int i=0;i<n;i++){
int min_ = INF,min_j = -1;
for(int j=0;j<n;j++)
if(!vis[j] && min_ > dis[j]){
min_ = dis[j];
min_j = j;
}
if(min_j == -1) break;
vis[min_j] = true;
for(int j=0;j<n;j++){
if(dis[j] > e[min_j][j]+dis[min_j]){
dis[j] = e[min_j][j]+dis[min_j];
pre[j].clear();
pre[j].push_back(min_j);
}
else if(dis[j] == e[min_j][j]+dis[min_j])
pre[j].push_back(min_j);
}
}
// for(auto item:pre[d])
// cout << item << "\t";
vector<int> temp_vec;
dfs(d,temp_vec);
reverse(path.begin(),path.end());
for(auto item:path)
cout << item << " ";
cout << dis[d] << " ";
cout << min_cost;
return 0;
}
一、定義和初始化
首先對于最短路徑的題，選擇
e[][]
來存圖。大小就是題目給的最大結點數+一點點。
然後就需要定義下面這些的變量
int dis[510]; // 存儲起點到每個點的最短距離
bool vis[510]; // 存儲是否通路某個節點
vector<int> pre[510]; // 存儲前置節點
// （如果隻有Dijkstra，用不上這個，這個是連接配接Dijkstra和DFS的橋梁）
首先要初始化
vis[]
全為
false
，還未通路（定義的時候已經自動初始化了），還有就是
dis[]、e[][]
全為INF。
還有就是正确的讀入資料，儲存到
e[][]
中了，有些題有點權，那麼就需要定義一個
weight[]
儲存點的權重。
30行代碼寫出來了。。。/w\
二、Dijkstra算法
這個在了解的基礎上直接背:
dis[起點]
為0
循環
n
（結點數）次， 在循環體中選擇
未通路的，最小dis[]
的結點
根據選擇的結點
更新各個結點的dis[]
如果需要儲存前置結點，則在更新
dis[]
時，更新
pre
具體看上面的代碼。
再加上20行代碼。。。
二.五、檢查pre
這個很重要，因為pre馬上要用于DFS了，我們可以在寫DFS前檢查下，方法很簡單
// for(auto item:pre[d])
// cout << item << "\t"
不出意外會列印結點d的前置結點。如果出了意外，回去仔細檢查Dijkstra有沒有那裡寫錯了。
三、DFS算法
如果隻求點到點的最短距離，那麼是不需要DFS，出現DFS一般就是點到點的最短距離不
unique
，需要根據點權或者像上面這道題的邊的其他權重來确定唯一的路徑。（都是套路）
但是DFS還是需要大家對遞歸和回溯有比較好的掌握的，比如記得
pop_back
什麼的。比較統一的寫法是，遞歸結束條件一般都是
回到了起點
。在這個時候根據
遞歸參數
儲存的值來更新結果。
具體看上面的代碼。
四、列印結果
這個就自己寫了。。。
總結，作者水準有限，有哪裡有問題都歡迎評論指出。如果對你有幫助歡迎點贊。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)