立志用最少的代碼做最高效的表達

---

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

輸入格式:
輸入說明：輸入數據的第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模板題。

dijkstra求解單源最短路徑的效率非常高。

步驟：
1、初始化（初始化地圖，初始化起點到其他點的距離）
2、調用dijkstra：首先遍歷起點周圍的所有點，找到距它最短的點，加入到點集中。 其次更新從點集到其他點的最短距離。

有不懂的地方歡迎評論區留言~

---

#include<iostream> #include<cstdio> using namespace std;const int INF = 0x3f3f3f3f; int ways[505][505][2]; //儲存路徑長度，費用 int dist[505], cost[505]; //存儲由st出發到各點最短路徑及費用 bool visit[505] = {false}; int n,m,st,ov;void dijkstra() {visit[st] = true; //先將起始點加入集合。int minpoint;for(int i1 = 0; i1 < n; i1++) {minpoint = n; //編號為n的城市不存在，st到n距離為inffor(int i = 0; i < n; i++) {if((!visit[i]) && (dist[i] < dist[minpoint])) minpoint = i;}if(minpoint == n) break; //沒找到，證明無連接，結束循環visit[minpoint] = true;for(int i = 0; i < n; i++) {//如果該點沒被訪問，且以新加入節點為路徑遍歷得到的值更小，則更新最小值 if(!visit[i] && (dist[i] > dist[minpoint] + ways[minpoint][i][0])) { dist[i] = dist[minpoint] + ways[minpoint][i][0];cost[i] = ways[minpoint][i][1] + cost[minpoint];}//如果距離相等，但花費更小，則更新最小花費。 else if(!visit[i] && (dist[i] == dist[minpoint] + ways[minpoint][i][0])&& (cost[i] > cost[minpoint] + ways[minpoint][i][1]))cost[i] = (cost[minpoint] + ways[minpoint][i][1]);} } }//對地圖初始化，都設為無限大。 void init_graph() {for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)ways[i][j][0] = ways[i][j][1] = INF; } //對從起點到任意點的距離初始化。 void init_d_c() {for(int i = 0; i < n; i++) {dist[i] = ways[st][i][0];cost[i] = ways[st][i][1];} }int main() {cin >> n >> m >> st >> ov;int a, b, c, d;init_graph();for(int i = 0; i < m; i++) {cin >> a >> b >> c >> d;ways[a][b][0] = ways[b][a][0] = c;ways[a][b][1] = ways[b][a][1] = d;}init_d_c();dist[n] = INF; //此不存在城市的最短路為INF dist[st] = cost[st] = 0; //到自身的最短路和花費為0dijkstra();cout << dist[ov] << ' ' << cost[ov]; return 0; }

---

耗時

---

修煉愛情的心酸
學會放好以前的渴望
我們那些信仰 要忘記多難
遠距離的欣賞 近距離的迷惘
誰說太陽會找到月亮
別人有的愛
我們不可能模仿

修煉愛情的悲歡
我們這些努力不簡單
快樂煉成淚水
是一種勇敢
幾年前的幻想 幾年后的原諒
為一張臉去養一身傷
別講想念我 我會受不了這樣… …

總結

以上是生活随笔為你收集整理的【dijkstra模板】旅游规划 (25 分)的全部內容，希望文章能夠幫你解決所遇到的問題。

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