题目要求:
现有N个城市,M条路线,并给出M条路线的间隔和消耗,当初给定终点S和起点D,要求求出终点到起点最短门路、最短距离和消耗,若有多条输入消耗最小的
算法思路:
这个是单源最短距离问题，这里应用Dijkstra算法的进行求解，这里须要求解的信息次要有三个，而且存在两个不同优先级的约束条件，那么咱们先应用Dijkstra算法求解取得具备最短距离的所有最短
门路，而后应用深度优先遍历所有的最短门路，在其余找出消耗最小的门路即为所求。
数据的存储:
这里应用c数组保留每一个城市到终点的最小消耗，cost数组保留任意两个城市之间的消耗 ，pre数组保留每个结点的前驱结点
Dijkstra算法求解
咱们循环N次，每一次循环，首先从所有未拜访的点中找到间隔终点最小的点nearest,而后再优化借助nearest到其余未拜访的点的最短距离，如果借助nearest达到以后点j更短，
那么就更新达到j的最短距离，最小消耗和达到j的前驱节点。如果最短距离一样然而通过nearest达到j的消耗更小，那么就更新达到j的最小消耗和j的前驱节点。
DFS搜寻：
咱们从起点开始搜寻，每次递归就拜访该节点，晓得遇到终点，达到递归边界，shortest保留以后搜寻的最短门路，遍历以后门路上的每一条边，累加所有的边权取得总消耗，如果total_cost==c[D]阐明以后的是最优的，应用result保留最优门路，最初得将入栈节点退栈并返回，递归体为拜访每一个以后节点的前驱节点，拜访结束后也得退栈回溯。
留神点：
- 1、计算消耗的时候只需计算n-1条边，并且在输入的时候得倒着拜访。
提交后果：
AC代码：
#include<cstdio>#include<vector>#include<algorithm>using namespace std;int N,M,S,D;// 顶点数，边数，终点和起点。 int G[505][505];// 边权，其值示意为两点之间的间隔int cost[505][505];// 两点之间的消耗 bool visited[505];// 拜访标记数组int dis[505];// 每一个城市到终点的间隔int c[505];//每一个城市到终点的最小消耗vector<int> pre[505];// 保留每一个站点的前驱结点vector<int> shortest;//最短门路vector<int> result;// 最优门路void DFS(int start){ shortest.push_back(start); if(start==S){ // 以后结点是起点 int total_cost = 0; for(int i=shortest.size()-1;i>0;--i){ total_cost += cost[shortest[i]][shortest[i-1]]; } if(total_cost==c[D]){ // 以后的门路是最优的 result = shortest; } shortest.pop_back(); return; } for(int i=0;i<pre[start].size();++i){ DFS(pre[start][i]); } shortest.pop_back();} void Dijkstra(int start){ // 初始化 fill(dis,dis+505,0x3fffffff); dis[start] = 0; c[start] = 0; // 循环N次 for(int i=0;i<N;++i){ // 首先从所有未拜访的点中找到间隔终点最小的点 int nearest,minDis=0x3fffffff; for(int j=0;j<N;++j){ if(!visited[j]&&minDis>dis[j]){ nearest = j; minDis = dis[j]; } } if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 // 优化借助nearest到其余未拜访的点的间隔 visited[nearest] = true; for(int j=0;j<N;++j){ if(!visited[j]&&G[nearest][j]!=0){ if(dis[j]>dis[nearest]+G[nearest][j]){ dis[j] = dis[nearest]+G[nearest][j]; c[j] = c[nearest] + cost[nearest][j]; pre[j].clear(); pre[j].push_back(nearest); }else if(dis[j]==dis[nearest]+G[nearest][j]&&c[j]>c[nearest]+cost[nearest][j]){ c[j] = c[nearest] + cost[nearest][j]; pre[j].push_back(nearest); } } } } } int main(){ scanf("%d %d %d %d",&N,&M,&S,&D); int a,b,distance,C; for(int i=0;i<M;++i){ scanf("%d %d %d %d",&a,&b,&distance,&C); G[b][a] = G[a][b] = distance; cost[b][a] = cost[a][b] = C; } Dijkstra(S); DFS(D); for(int i=result.size()-1;i>=0;--i){ printf("%d ",result[i]); } printf("%d %d",dis[D],c[D]); return 0;}