有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数NN、MM、SS、DD，其中NN（2le Nle 5002≤N≤500）是城市的个数，顺便假设城市的编号为0~(N-1N−1)；MM是高速公路的条数；SS是出发地的城市编号；DD是目的地的城市编号。随后的MM行中，每行给出一条高速公路的信息，分别是：城市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
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstring>
#include <stack>
#define INF 100000
using namespace std;
/* 题意要求： 保证最短距离，若距离相等 则选取总价格最低的路径
1. dijkstra找最短路 一个新节点加入已找到最短路径的集合S后 更新其他所有点的权重时 需要增加一种情况 就是当距离不变时 更新价格为较小的
那条路的价格 。
*/
class Graph{
private:
int V;
int E;
int** dis; //城市之间的距离
int** cost; //城市之间的路费
int* collected; //判断该点是否已经求出最短路
int* dist; //出发点s到图中每个城市的最短距离
int* cos; //出发点s到图中每个城市的最短路费
public:
//构造函数
Graph(int v,int e){
this->V = v;
this->E = e;
this->dis = new int*[V];
this->cost = new int*[V];
this->collected = new int[V];
this->dist = new int[V];
this->cos = new int[V];
for ( int i = 0 ; i < this->V ; i ){
this->dis[i] = new int[this->V];
this->cost[i] = new int[this->V];
this->collected[i] = 0;
for ( int j = 0 ; j < this->V ; j ){
this->dis[i][j] = INF;
this->cost[i][j] = INF;
}
}
for ( int i = 0 ; i < this->E ; i ){
int a,b,c,d;
cin>>a>>b>>c>>d;
this->dis[a][b] = this->dis[b][a] = c;
this->cost[a][b] = this->cost[b][a] = d;
}
}
//初始化最短距离和最短路费
void Init(int s){
for ( int i = 0 ; i < this->V ; i ){
dist[i] = this->dis[i][s];
this->cos[i] = this->cost[i][s];
}
}
//s为出发点，d为目的点，利用Dijkstra求最短距离和最少路费
void Dijkstra(int s){
int v;
this->Init(s);
//先将起点收入集合
dist[s] = 0; //初始状态 v节点属于集合
this->collected[s] = 1;
for ( int k = 0 ; k < this->V ; k ){//开始主循环 每次求得v到某个顶点的最短路径 并加v到集合
int MIN = INF; //当前所知离v0最近的节点
int v;
for (int j = 0 ; j < V ; j ){
if ( !this->collected[j] && this->dist[j] < MIN){
MIN = dist[j]; //找到最短路径节点
v = j;
}
}
this->collected[v] = 1;
for ( int i = 0 ; i < this->V ; i ){ //更新当前的最短路径
if( !this->collected[i] && MIN this->dis[v][i] < dist[i]){
this->dist[i] = MIN this->dis[v][i];
this->cos[i] = this->cos[v] this->cost[v][i];
}else if(!this->collected[i] && MIN this->dis[v][i] == dist[i]
&& this->cos[i] > this->cos[v] this->cost[v][i]){
//路径长度相等则选择价格较便宜的一条
this->cos[i] = this->cos[v] this->cost[v][i];
}
}
}
}
void Print(int d){
cout<<this->dist[d]<<" "<<this->cos[d]<<endl;
}
};
int main()
{
int v,e,s,d;
cin>>v>>e>>s>>d;
Graph graph(v,e);
graph.Dijkstra(s);
graph.Print(d);
return 0;
}
