資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究尋找使用火車到達目的地所需的最少成本
對於這個問題，旅途中有 N 個站點。車輛從站點 0 開始，到站點 N-1。在表中，給出所有車站之間成對的車票價格。我們必須找出以所給價格抵達目的地所需的最低價格。
輸入和輸出
Input: The cost matrix of the journey. 0 15 80 90 ∞ 0 40 50 ∞ ∞ 0 70 ∞ ∞ ∞ 0 Output: The minimum cost is 65. At first go to the destination 1 from 0. (cost 15), then 1 to 4 (cost 50). So total cost 65.
演算法
findMinCost(cost)
輸入 −從每個起點到每個目的地的成本矩陣。
輸出 −找出達到目的地的最低成本。
Begin define array costLoc, whose size is same as sumber of locations, fill costLoc with ∞. n := number of locations costLoc[0] := 0 for each source i to each destination j, do if costLoc[j] > costLoc[i] + cost[i, j], then costLoc[j] := costLoc[i] + cost[i, j] done return costLoc[n-1] End
示例
#include<iostream>
#define INF INT_MAX
#define NODE 4
using namespace std;
int cost[NODE][NODE] = {
{0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
int findMinCost() { //find smallest possible cost to reach destination
int costStation[NODE]; //store cost to reach any station from 0
for (int i=0; i<NODE; i++)
costStation[i] = INF; //initially all are infinity
costStation[0] = 0; //cost for station 0 is 0 as it is starting point
for (int i=0; i<NODE; i++)
for (int j=i+1; j<NODE; j++)
if (costStation[j] > costStation[i] + cost[i][j]) //find intermediate station for min cost costStation[j] = costStation[i] + cost[i][j];
return costStation[NODE-1];
}
int main() {
cout << "The Minimum cost to reach station " << NODE << " is " << findMinCost() << endl;
return 0;
}輸出
The Minimum cost to reach station 4 is 65
更新於： 16-06-2020
552 次閱讀
廣告