共计 2260 个字符，预计需要花费 6 分钟才能阅读完成。
题目要求:
现有 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;
}
正文完
