1030 Travel Plan
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 (≤) 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
题意:
最短路问题。
思路:
这道题用到了Dijkstra算法和DFS算法,想要解这道题还得要完全的搞明白Dijkstra算法寻找最短路的原理。Dijkstra算法的工作原理是从起点开始不断地向外拓展与起点相连的点,然后在这些点中找出到起点距离最短的点,以此为新的起点再向外拓展,直至遍历完图中的每一个结点。遍历的过程中需要记录到该结点最短路径的前驱结点。因为这样的结点可能不止一个,所以需要用一个与这个结点相关的数组专门存储。
遍历完图中的每一个节点后,也就把到每一结点的最短路径记录下来了。然后通过DFS从终点开始反向遍历,寻找花费最小的最短路径。
本题用邻接矩阵来表示图的信息。
Code:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int inf = 0x7fffffff; 6 7 int n, m, s, d; 8 // 用来存储图的信息 9 vector<vector<int> > grap(505, vector<int>(505, inf)); 10 // 用来存储图中每条边的花费 11 vector<vector<int> > cost(505, vector<int>(505, inf)); 12 // 用来标记图中的那个结点是否已经被访问过 13 vector<bool> visited(505, false); 14 // 记录每个结点到达起点的位置 15 vector<int> dis(505, inf); 16 // 用来存储最短路径的信息 17 vector<int> path, tempPath; 18 // 记录每个结点的前驱结点 19 vector<int> pre[505]; 20 int minCost = inf; 21 22 void dfs(int v) { 23 tempPath.push_back(v); 24 if (v == s) { 25 int tempCost = 0; 26 int tempDis = 0; 27 int len = tempPath.size(); 28 for (int i = len - 1; i > 0; --i) { 29 tempCost += cost[tempPath[i]][tempPath[i - 1]]; 30 } 31 if (minCost > tempCost) { 32 minCost = tempCost; 33 path = tempPath; 34 } 35 tempPath.pop_back(); 36 return; 37 } 38 for (int it : pre[v]) dfs(it); 39 tempPath.pop_back(); 40 } 41 42 int main() { 43 cin >> n >> m >> s >> d; 44 int c1, c2, t, money; 45 for (int i = 0; i < m; ++i) { 46 cin >> c1 >> c2 >> t >> money; 47 grap[c1][c2] = grap[c2][c1] = t; 48 cost[c1][c2] = cost[c2][c1] = money; 49 } 50 dis[s] = 0; 51 pre[s].push_back(s); 52 // 运用Dijkstra算法寻找每个结点到起点的最小距离。 53 for (int i = 0; i < n; ++i) { 54 int u = -1, minn = inf; 55 for (int j = 0; j < n; ++j) { 56 if (visited[j] == false && dis[j] < minn) { 57 u = j; 58 minn = dis[j]; 59 } 60 } 61 // 表明与起点联通的结点已经遍历完毕 62 if (u == -1) break; 63 visited[u] = true; 64 // 寻找与u相连的结点,并更新其最短距离 65 for (int j = 0; j < n; ++j) { 66 if (visited[j] == false && grap[u][j] != inf) { 67 if (dis[j] > dis[u] + grap[u][j]) { 68 dis[j] = dis[u] + grap[u][j]; 69 pre[j].clear(); 70 pre[j].push_back(u); 71 } else if (dis[j] == dis[u] + grap[u][j]) { 72 pre[j].push_back(u); 73 } 74 } 75 } 76 } 77 dfs(d); 78 79 for (int i = path.size() - 1; i >= 0; --i) cout << path[i] << " "; 80 cout << dis[d] << " " << minCost << endl; 81 82 return 0; 83 }
虽然知道这是使用那种算法,但是写代码的时候还是不知道从哪里开始写。
参考:
https://www.liuchuo.net/archives/2369
相关文章
- HVP plan
- Working Plan 优先队列+贪心
- EXPLAIN PLAN FOR 和 SET AUTOTRACE之间的差别
- oracle:查看sql执行计划 explain PLAN FOR
- 2014--My Plan
- execution plan
- PgSQL · 特性分析 · Plan Hint
- execution plan
- PostgreSQL plan cache 源码浅析 - 如何确保不会计划倾斜
- SAP ABAP SQL的execution plan和cache
- Create Live rate plan job and how to do trouble shooting
- when is One Order gt_plan_exets filled
- 创建Live Rates Plan时Sales Organization无法自动带出来的问题
- hdi-shared Service plan的分配
- PostgreSQL plan cache 源码浅析 - 如何确保不会计划倾斜
- 【codeforces 742C】Arpa's loud Owf and Mehrdad's evil plan
- cannot fetch plan for SQL_ID: 5qgz1p0cut7mx, CHILD_NUMBER: 0
- 十八般武艺玩转GaussDB(DWS)性能调优:Plan hint运用
- Sql_Handle and Plan_Handle Explained
- 软件架构师成长之路: Master Plan for becoming a Software Architect
- Oracle Quality --- Setup Collection Element and Collection Plan
- POJ 2175 Evacuation Plan (费用流,负环,消圈法,SPFA)
- Oracle SQL操作计划基线总结(SQL Plan Baseline)
- 年假小 Plan
- 谣言检测(PLAN)——《Interpretable Rumor Detection in Microblogs by Attending to User Interactions》
- 用conda安装包出现The environment is inconsistent, please check the package plan carefully
- [to do list][PCB][questions]and[plan]
- PAT 1030 Travel Plan[图论][难]
- Adaptive SQL Plan Management (SPM)