C++PTA A1030(Dijkstra+dfs)

C++PTA A1030(Dijkstra+dfs)

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.

输入要求：每个文件包含四个整数N、M、S、D N是城市的数量，从0到N-1，M是高速公路的书来那个，S和D是开始和目的，紧接着M行，提供的高速公路信息是这样的，城市1 城市2 距离 成本 数字不会超过五百。分隔之间有空格

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

核心思路

输入四个，一遍Dijkstra算法走一遍，dfs进行输出。

完整源码

#include
#include
#include
using namespace std;
const int MAXV   = 510;
const int INF = 1000000000; //无穷大

//n为顶点数,m为边数,st和ed分别为起点和终点
//G为距离矩阵，cost为花费矩阵
//d[]记录最短距离，c[]记录最小花费
int n,m,st,ed,G[MAXV][MAXV],cost[MAXV][MAXV];
int d[MAXV],c[MAXV],pre[MAXV];
bool vis[MAXV] ={false}; //vis[i]==true; 表示顶点i已访问，初值均为false


void Dijkstra(int s){
    fill(d,d+MAXV,INF);
    fill(c,c+MAXV,INF);
    for(int i =0;i 
dfs版本
 
#include
#include
#include
#include
using namespace std;
const int MAXV = 510; //最大顶点数
const int INF =  100000000;//无穷大

//n为定点数,m为边数,st和ed为起点与终点
//G为距离矩阵,const为花费矩阵
//fill记录最短距离,minCost 记录最短路径上的最小话费
int n,m,st,ed,G[MAXV][MAXV],cost[MAXV][MAXV];
int d[MAXV],minCost = INF;
bool vis[MAXV] = {false}; //vis[i]== true表示顶点已访问,初值均为false
vector pre[MAXV]; //前驱
vector tempPath,path; //临时路径及最优路径

void Dijkstra(int s){
    fill(d,d+MAXV,INF); // fill函数将整个d数组赋为INF(慎用memset)
    d[s] = 0;//起点s到达自身的距离为0
    for(int i = 0;i0;i--){
            int id = tempPath[i],idNext = tempPath[i-1];
            tempCost += cost[id][idNext]; //增加边id->idNext 的边权
        }
        if(tempCost < minCost) {
            minCost = tempCost; //更新minCost
            path = tempPath; //更新path
        }
        tempPath.pop_back();
        return ;
    }
    tempPath.push_back(v);
    for(int i= 0;i= 0;i--){
        printf("%d ",path[i]);
    }
    printf("%d %dn",d[ed],minCost);
    return 0;
}

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5715086.html