链接：PAT Advanced 1030
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
题意：
有N个城市（编号为0 ~ N-1），M条道路（无向边），并给出M条道路的距离与花费。现给定起点S和终点D，求从起点到终点的最短路径，最短距离及花费。（花费是以路径最短为前提的最少花费）（如果有多条最短路径，则选择花费最少的那条）
分析：
dijkstra算法，用于解决单源最短路（路权为正）问题，用pre[maxn]数组来记录路径，记录每个结点的前驱结点。
以下代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1000000000;
const int maxn=510;
struct highway
{
int D; //该道路的距离int C; //该道路的花费highway(){
D=-1; //D初始化为-1，代表两结点间无通路}
};
int N,d[maxn],c[maxn],pre[maxn]; //d为起点到各结点的 最短距离
bool vis[maxn]={
false}; //c为起点到各结点 距离最短的前提下 的 最少花费
highway G[maxn][maxn]; //邻接矩阵
void Dijkstra(int s)
{
fill(d,d+N,INF); //最短距离d初始化为INFfill(pre,pre+N,-1); //pre均初始化为-1，代表无前驱结点d[s]=0; //起点s到自身距离为0c[s]=0; //起点s到自身花费为0for(int i=0;i<N;i++) //每次访问一个结点，访问N次{
int u,MIN=INF;for(int j=0;j<N;j++) //在未访问结点中找到 d最小的结点u{
if(!vis[j]&&d[j]<MIN){
MIN=d[j];u=j;}}vis[u]=true; //访问 ufor(int v=0;v<N;v++) //以 u为踏板优化 u可以到达的结点{
if(!vis[v]&&G[u][v].D!=-1) //如果 未访问 且 可到达{
if(d[u]+G[u][v].D<d[v]) //如果可优化（距离更短）{
d[v]=d[u]+G[u][v].D; //距离更新c[v]=c[u]+G[u][v].C; //花费一同更新pre[v]=u; //记录 v的前驱结点为 u}else if(d[u]+G[u][v].D==d[v]&&c[u]+G[u][v].C<c[v]){
//如果距离相等 但花费更小c[v]=c[u]+G[u][v].C; //花费更新pre[v]=u; //记录 v的前驱结点为 u} }}}
}
void print_path(int x) //利用递归输出路径
{
if(x==-1)return;elseprint_path(pre[x]);printf("%d ",x); //printf放在最后
}
int main()
{
int M,S,D;scanf("%d %d %d %d",&N,&M,&S,&D);for(int i=0;i<M;i++){
int u,v,a,b;scanf("%d %d %d %d",&u,&v,&a,&b);G[u][v].D=G[v][u].D=a;G[u][v].C=G[v][u].C=b;}Dijkstra(S);print_path(D);printf("%d %d",d[D],c[D]);return 0;
}