[PAT A1030]Travel Plan
题目描述
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.
输入格式
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.
输出格式
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.
输入样例
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20输出样例
0 2 3 3 40解析
1.题目大意：这道题目读懂的难度不算大，首先给出n,m,s,d，n表示结点个数，m表示边数，s表示起点，d表示终点，然后下面n行给出边的起点和终点，以及每条边的花费。要我们输出最短路径，如果有多条的话，输出花费最少的路径。
2.没有特别难的地方，就是使用Dijkstra+DFS,主要是使用模板（这个模板需要熟练敲出，用处很大）：
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 510;
const int INF = 1000000000;
int Graph[maxn][maxn], Cost[maxn][maxn]; //存储图路径长的数组和存储路径花费的数组
int d[maxn]; //最短路径长数组
bool visit[maxn]; //某一点有没有被访问过
vector<int> pre[maxn]; //最短路径存储先驱结点的数组
vector<int> temproad, road; //存放当前路径和最短路径的数组
int mincost=INF;
int n, m, start, dest;
void Dijkstra(int s);
void DFS(int v);
int main()
{fill(Graph[0], Graph[0] + maxn * maxn, INF);fill(Cost[0], Cost[0] + maxn * maxn, INF);fill(d, d + maxn, INF);scanf("%d%d%d%d", &n, &m, &start, &dest);for (int i = 0; i < m; i++) {int st, de, dis, cost;scanf("%d%d%d%d", &st, &de, &dis, &cost);Graph[st][de] = Graph[de][st] = dis;Cost[st][de] = Cost[de][st] = cost;}Dijkstra(start);DFS(dest);for (int i = road.size() - 1; i >= 0; i--) {printf("%d", road[i]);if (i != 0) printf(" ");}printf(" %d %d", d[dest], mincost);return 0;
}
void Dijkstra(int s) {d[s] = 0; //初始结点最短路径找到，就是他自己，并设置d[s]=0for (int i = 0; i < n; i++) { //找到未访问的，当前最短路径长的结点int u = -1, min = INF;for (int j = 0; j < n; j++) {if (d[j] < min && visit[j] == false) {u = j;min = d[j];}}if (u == -1) return; //没找到，返回visit[u] = true; //设置该结点已访问for (int v = 0; v < n; v++) {if (Graph[u][v] != INF && visit[v] == false) { //找到一条更短的路径if (Graph[u][v] + d[u] < d[v]) {d[v] = Graph[u][v] + d[u];pre[v].clear(); //覆盖prepre[v].push_back(u); //存放上一个结点}else if (Graph[u][v] + d[u] == d[v]) { //找到一条和最短路径相同长的路径pre[v].push_back(u); //pre先驱结点增加1个}}}}
}
void DFS(int v) {if (v == start) { //如果已经到起点，计算cost并比较mincostint cost = 0;temproad.push_back(v);for (int i = temproad.size() - 1; i >= 1; i--) {int id1 = temproad[i];int id2 = temproad[i - 1];cost += Cost[id1][id2];}if (cost < mincost) {mincost = cost;road = temproad;}temproad.pop_back();return;}temproad.push_back(v);for (int i = 0; i < pre[v].size(); i++) DFS(pre[v][i]);temproad.pop_back();}