PAT A1030_综合

1030 Travel Plan (30分)

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:

Sample Output:

0 2 3 3 40

第一次解答：Dijkstra

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;#define MAXV 510
#define INF 1000000000int N,M,S,D;int G[MAXV][MAXV];
bool vis[MAXV] = {
    false};int cost[MAXV][MAXV];int d[MAXV];
int c[MAXV];int pre[MAXV];void Dijkstra(int s)//求出的是到达其他顶点的最短路径d[],最小花费cost[]，到达其他顶点的路径pre[]
{
    int i;fill(d,d+MAXV,INF);fill(c,c+MAXV,INF); //Q:注意：这行代码是否需要 A:肯定是需要的，来更新c[]的值，不然更新不了（初始化的c[]都是0，不会再进行更新）for(i = 0;i<N;i++) pre[i] = i; d[s] = 0;c[s] = 0;for( i = 0;i<N;i++){
    int u = -1,MIN = INF;for(int j = 0;j<N;j++){
    if(vis[j] == false && d[j] < MIN){
    u = j;MIN = d[j];}}if(u == -1) return ;vis[u] = true;for(int v = 0;v<N;v++){
    if(vis[v] == false && G[u][v] != INF){
    if(d[v] > d[u] + G[u][v]){
    pre[v] = u;d[v] = d[u] + G[u][v];c[v] = c[u] + cost[u][v];}else if(d[v] == d[u] + G[u][v] && c[v] > c[u] + cost[u][v]){
    c[v] = c[u] + cost[u][v];pre[v] = u;}}}}
}//Q：现在保存了路径之后,如何输出这条路径？并且计算出所需要的条件，例如一条路径上的所有权重和花费？
//A：既然知道了这条路径，那么就会知道最后的终点D,通过d[D]和c[D]来计算这条路径的权重和花费。void DFS(int s,int v)//既然使用递归，就要有一个元素保存当前的状态，就本题而言是当前要访问的节点（输出的时候就是v）
{
    if(v == s){
    printf("%d ",v);return ;}DFS(s,pre[v]);printf("%d ",v);
}int main()
{
    int i;//FILE *fp;//fp = fopen("data.txt","r");//fscanf(fp,"%d%d%d%d",&N,&M,&S,&D);scanf("%d%d%d%d",&N,&M,&S,&D);fill(G[0],G[0] + MAXV*MAXV,INF);//这行添加的原因是，在更新d[],c[],pre[]的时候需要判断是否有边相连//fill(cost[0],cost[0] + MAXV*MAXV,INF);//Q:是否需要添加 A:无需添加，因为有G[][]->cost[][]for(i = 0;i<M;i++){
    int u,v;//fscanf(fp,"%d%d",&u,&v);scanf("%d%d",&u,&v);//fscanf(fp,"%d%d",&G[u][v],&cost[u][v]);scanf("%d%d",&G[u][v],&cost[u][v]);G[v][u] = G[u][v];cost[v][u] = cost[u][v];}Dijkstra(S);DFS(S,D);printf("%d %d\n",d[D],c[D]);return 0;
}

Dijkstra的意义
计算到各个节点的最短距离d[]和最小花费c[],以及符合当前所有标尺的最佳路径pre[]（首先需要明白，S->D中存在着多条最短路径，这些最短路径的距离是相同的，pre[]中存放的是众多最短路径中的符合其他标尺的一条）
已知终点和起点如何求路径，以及这条路径上的weight和cost
计算路径需要通过DFS（int s,int v）；
改路径上的权重和花费通过d[]和c[]即可
fill(c,c+MAXV,INF);这行代码是肯定需要写的
因为如果不进行初始化INF，那么在有多条最短路径的时候无法更新c[]数组
c[v] > c[u] + cost[u][v]一定不成立
fill(G[0],G[0] + MAXV*MAXV,INF)这行代码需要写，
因为需要判断节点之间是否相连
fill(cost[0],cost[0] + MAXV*MAXV,INF);不需要编写
使用cost[][]的地方，前提是G[][] != INF，保证了cost[][]一定存在。
pre[]数组是否需要初始化？或者说为什么要初始化。
1.首先告诉你for(i = 0;i<N;i++) pre[i] = i;这行代码如果注释掉执行，在PAT中运行完全正确
2.这样初始化的意义是将每一个节点的前驱指向自身。
3.个人觉着这行代码，就运行的结果而言，写或者不写，答案是相同的。题目中编写的原因可能就是单纯的为了初始化。你要是自己画图分析一下也是这样的结果，因为DFS[]遍历的时候pre[v] == S,直接就到达递归边界了，不会再进行pre[S]递归。
为了规范化还是编写吧。可以与下面的写法相比较，下面的刚开始没有初始化，是因为会调用pre[v].clear(),就间接的完成初始化。
第二次解答：Dijkstra + DFS
这种做法的好处是在Dijkstra算法中可以专注于所有路径的求解
利用DFS来计算满足其他条件的唯一路径。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;const int MAX = 510;
const int INF = 1000000000;int N,M,S,D;int G[MAX][MAX];
bool vis[MAX] = {
    false};int cost[MAX][MAX];int d[MAX];vector<int> pre[MAX];
int minCost = INF;
vector<int> tempPath,path;void Dijkstra(int s)
{
    fill(d,d + MAX,INF);d[s]  = 0;for(int i = 0;i<N;i++){
    int u = -1,MIN = INF;for(int j = 0;j<N;j++){
    if(vis[j] == false && d[j] < MIN){
    u = j;MIN = d[j];}}if(u == -1) return ;vis[u] = true;for(int v = 0;v<N;v++){
    if(d[v] > d[u] + G[u][v]){
    d[v] = d[u] + G[u][v];pre[v].clear();pre[v].push_back(u);}else if(d[v] == d[u] + G[u][v]){
    pre[v].push_back(u);}}}
}void DFS(int s,int v)
{
    if(v == s){
    tempPath.push_back(v);int tempCost = 0;for(int i = tempPath.size() - 1;i>0;i--){
    int id = tempPath[i],idNext = tempPath[i-1];tempCost += cost[id][idNext];}if(tempCost < minCost){
    minCost = tempCost;path = tempPath;}tempPath.pop_back();return;}tempPath.push_back(v);for(int i = 0;i<pre[v].size();i++){
    DFS(s,pre[v][i]);}tempPath.pop_back();
}
int main()
{
    int i,j;scanf("%d%d%d%d",&N,&M,&S,&D);fill(G[0],G[0] + MAX*MAX,INF);fill(cost[0],cost[0] + MAX*MAX,INF);//单纯的为了初始化for(i = 0;i<M;i++){
    int u,v;scanf("%d%d",&u,&v);scanf("%d%d",&G[u][v],&cost[u][v]);G[v][u] = G[u][v];cost[v][u] = cost[u][v];}Dijkstra(S);DFS(S,D);for(i = path.size() - 1;i>=0;i--){
    printf("%d ",path[i]);}printf("%d %d\n",d[D],minCost);return 0;
}