原题干：
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 (<=500) 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
大意：
旅行计划！第一行给出"城市数量 道路数量 起点 终点"
接下来有几条道路就给出几行数字，每行有4个数字，分别是：
"起始城市 终止城市 距离 路费"
要求你规划出一条从起点到终点，距离最近的路线，在距离最近的基础上找到消费最少的路线，
然后输出路线，最后给出路程的距离与消费多少。
一道很有趣的最短路径类问题，使用Dijkstra算法就可以啦
至于记录距离，我们可以使用"前驱数组"法来记录，具体看这里：https://www.mmuaa.com/post-218.html
代码如下：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 510
#define INF 0x3fffffff
int G[MAXN][MAXN], C[MAXN][MAXN];
bool visited[MAXN] = {false};
int MinDistance[MAXN];
int startP, endP;
int RoadCnt, CityCnt;
int MinCost[MAXN];
int pre[MAXN];
void init(){
fill(MinDistance, MinDistance + MAXN, INF);
fill(MinCost, MinCost + MAXN, INF);
fill(G[0], G[0] + MAXN * MAXN, INF);
//设置前驱数组都是自己本身
for(int i = 0; i < CityCnt; i++)
pre[i] = i;
}
void Dijkstra(int s){
//init
MinCost[s] = 0;
MinDistance[s] = 0;
for(int i = 0; i < CityCnt; i++){
//find the min-dis point in MinDistance
int p = -1, MIN = INF;
for(int j = 0; j < CityCnt; j++)
if(visited[j] == false && MinDistance[j] < MIN)
p = j, MIN = MinDistance[j];
if(p == -1) return;
//found
visited[p] = true;
//Use Point-p as medi-point to Update Point-j
for(int j = 0; j < CityCnt; j++){
if(visited[j] == false && G[p][j] != INF){
//find a better way
if(MinDistance[p] + G[p][j] < MinDistance[j]){
MinDistance[j] = MinDistance[p] + G[p][j];
MinCost[j] = C[p][j] + MinCost[p];
pre[j] = p;
}
//if find a alike way
else if(MinDistance[p] + G[p][j] == MinDistance[j] \
&& MinCost[j] > C[p][j] + MinCost[p])
MinCost[j] = C[p][j] + MinCost[p], pre[j] = p;
}
}
}
}
void DFS(int p){
if(p == startP){
cout << startP << " ";
return;
}
DFS(pre[p]);
cout << p << " ";
}
int main(){
cin >> CityCnt >> RoadCnt >> startP >> endP;
init();
for(int i = 0; i < RoadCnt; i++){
int _, __;
cin >> _ >> __;
cin >> G[_][__] >> C[_][__];
G[__][_] = G[_][__], C[__][_] = C[_][__];
}
Dijkstra(startP);
DFS(endP);
cout << MinDistance[endP] << " " << MinCost[endP] << endl;
return 0;
}