PAT 甲级 A1030

题目连接

1030 Travel Plan (30分)

题目大意

给定输入输出格式，输出源结点到目标结点的最短路径、距离、cost。若最短路径有多条，则输出cost之和最少的那条

思路

在原来邻接表的基础上，增多一个cost表示花费，并且设置vector<int>pre[maxn]来表示结点最短路径的前驱(因为从源节点到目标结点的最短路径可能有多条，因此pre[i]表示的是结点i所有最短路径的前驱)

/*边定义*/
struct arc
{
    int dis, cost;
}V[maxn][maxn];

使用dijkstra算法求解出所有的最短路径后，再使用DFS算法求出cost最少的路径，写法如下:

/*root表示的是当前结点, s表示起始结点*/
vector<int> path, temp_path;
void DFS(int root) {
    //当前结点为起始节点时，为一条完整的最短路径(从目标结点开始回溯)if (root == s) {
    temp_path.push_back(root);int cost = 0;//计算当前路径成本costfor (int i = temp_path.size() - 1; i > 0 ; i--) {
    int cur = temp_path[i], next = temp_path[i - 1];cost += V[cur][next].cost;}if (cost < minCost) {
    minCost = cost;path = temp_path;}temp_path.pop_back();}else {
    temp_path.push_back(root);for (int i = 0; i < pre[root].size(); i++) {
    DFS(pre[root][i]);}temp_path.pop_back();}
}

AC代码

#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 505
#define INF ((1 << 31) - 1)
using namespace std;struct arc
{
    int dis, cost;
}V[maxn][maxn];int n, m, s, d, minCost = INF;
int dis[maxn];
vector<int> pre[maxn], path, temp_path;
bool visit[maxn] = {
     false };void Dijkstra() {
    fill(dis, dis + maxn, INF);dis[s] = 0;for (int i = 0; i < n; i++) {
    int u = -1, min = INF;for (int j = 0; j < n; j++) {
    if (!visit[j] && dis[j] < min) {
    min = dis[j];u = j;}}if (u == -1) return;visit[u] = true;for (int v = 0; v < n; v++) {
    if (!visit[v] && V[u][v].dis > 0) {
    if (dis[u] + V[u][v].dis < dis[v]) {
    dis[v] = dis[u] + V[u][v].dis;pre[v].clear();pre[v].push_back(u);}else if (dis[u] + V[u][v].dis == dis[v]){
    pre[v].push_back(u);}}}}
}void DFS(int root) {
    if (root == s) {
    temp_path.push_back(root);int cost = 0;//计算当前路径成本costfor (int i = temp_path.size() - 1; i > 0 ; i--) {
    int cur = temp_path[i], next = temp_path[i - 1];cost += V[cur][next].cost;}if (cost < minCost) {
    minCost = cost;path = temp_path;}temp_path.pop_back();}else {
    temp_path.push_back(root);for (int i = 0; i < pre[root].size(); i++) {
    DFS(pre[root][i]);}temp_path.pop_back();}
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &d);for (int i = 0; i < m; i++) {
    int u, v, dist, cost;scanf("%d%d%d%d", &u, &v, &dist, &cost);V[v][u].dis = V[u][v].dis = dist;V[v][u].cost = V[u][v].cost = cost;}Dijkstra();DFS(d);//打印路径for (int i = path.size() - 1; i >= 0 ; i--) {
    printf("%d ", path[i]);}printf("%d %d\n", dis[d], minCost);return 0;
}