題目：
有了一張自駕旅游路線圖，你會知道城市間的高速公路長度、以及該公路要收取的過路費。現在需要你寫一個程序，幫助前來咨詢的游客找一條出發地和目的地之間的最短路徑。如果有若干條路徑都是最短的，那么需要輸出最便宜的一條路徑。

輸入格式:
輸入說明：輸入數據的第1行給出4個正整數N、M、S、D，其中N（2≤N≤500）是城市的個數，順便假設城市的編號為0~(N?1)；M是高速公路的條數；S是出發地的城市編號；D是目的地的城市編號。隨后的M行中，每行給出一條高速公路的信息，分別是：城市1、城市2、高速公路長度、收費額，中間用空格分開，數字均為整數且不超過500。輸入保證解的存在。

輸出格式:
在一行里輸出路徑的長度和收費總額，數字間以空格分隔，輸出結尾不能有多余空格。

輸入樣例:

4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20

輸出樣例:

3 40

思路：
本題是經典的最短路徑模板題，用的是Dijkstra+Dfs的模板，具體求法可以見下面的代碼。對于這道題，這種做法可能有點顯得多余，但當出現了第二卡尺、第三卡尺的時候，以及題目要求輸出具體路徑時，Dijkstra+Dfs模板的優勢不言而喻。
當然劣勢是寫的代碼稍微得有些多~但是它簡單吶，簡單到無腦默寫即可！
我記得最近的天梯賽以及PAT考試挺久沒出最短路徑的題目了，而圖在天梯賽中占據了重要的地位，去年考了兩道圖的題，占了45分~盲猜今年會考一波最短路徑（沒考的話狗頭保命）

注明：
代碼中的三維數組，e[ ][ ][0]表示距離，e[ ][ ][1]表示收費價格。
path表示該節點的前驅節點，比如一條最短路徑v1 v2 v5中（v1是起點，v5是終點），則v5的前驅節點是v2。當然每個頂點的前驅節點不唯一。
函數Dijkstra（）做的事情就是找出所有的最短路徑，這個時候所有的卡尺（限制條件）是不用去考慮的哦。
函數Dfs則是在所有的最短路徑中找到最符合條件的一條。

代碼：

#include<bits/stdc++.h> using namespace std; int n, m, s, d, e[505][505][2]; vector<int> path[505], res, temppath; int vis[505], dis[505];void dijkstra(int v) {memset(dis, 0x3f3f3f3f, sizeof(dis));dis[v] = 0;for(int k = 0; k < n; k++){int u = -1, mind = 0x3f3f3f3f;for(int i = 0; i < n; i++){if(vis[i] == false && dis[i] < mind){mind = dis[i];u = i;}}if(u == -1)return;vis[u] = true;for(int j = 0; j < n; j++){if(vis[j] == false && e[u][j][0] != 0x3f3f3f3f){if(dis[u] + e[u][j][0] < dis[j]){path[j].clear();path[j].push_back(u);dis[j] = dis[u] + e[u][j][0];}else if(dis[u] + e[u][j][0] == dis[j])path[j].push_back(u);}}} }int minm = 0x3f3f3f3f; void dfs(int v) {temppath.push_back(v);if(v == s){int money = 0;for(int i = 1; i < temppath.size(); i++)money += e[temppath[i-1]][temppath[i]][1];if(money < minm){minm = money;res = temppath;}temppath.pop_back();return;}for(int i = 0; i < path[v].size(); i++)dfs(path[v][i]);temppath.pop_back(); }int main() {scanf("%d %d %d %d", &n, &m, &s, &d);memset(e, 0x3f3f3f3f, sizeof(e));int a, b, t1, t2;for(int i = 0; i < m; i++){scanf("%d %d %d %d", &a, &b, &t1, &t2);e[a][b][0] = e[b][a][0] = t1;e[a][b][1] = e[b][a][1] = t2;}dijkstra(s);dfs(d);printf("%d %d\n", dis[d], minm);return 0; }

總結

以上是生活随笔為你收集整理的数据结构 旅游规划（Dijkstra+Dfs)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。