乐趣区

关于算法-数据结构:PAT甲级1030-Travel-Plan

jiezi

题目要求:

现有 N 个城市,M 条路线, 并给出 M 条路线的间隔和消耗, 当初给定终点 S 和起点 D, 要求求出终点到起点最短门路、最短距离和消耗, 若有多条输入消耗最小的

算法思路:

这个是单源最短距离问题，这里应用 Dijkstra 算法的进行求解，这里须要求解的信息次要有三个，而且存在两个不同优先级的约束条件，那么咱们先应用 Dijkstra 算法求解取得具备最短距离的所有最短
门路，而后应用深度优先遍历所有的最短门路，在其余找出消耗最小的门路即为所求。

数据的存储:

这里应用 c 数组保留每一个城市到终点的最小消耗，cost 数组保留任意两个城市之间的消耗，pre 数组保留每个结点的前驱结点

Dijkstra 算法求解

咱们循环 N 次，每一次循环，首先从所有未拜访的点中找到间隔终点最小的点 nearest, 而后再优化借助 nearest 到其余未拜访的点的最短距离，如果借助 nearest 达到以后点 j 更短，
那么就更新达到 j 的最短距离，最小消耗和达到 j 的前驱节点。如果最短距离一样然而通过 nearest 达到 j 的消耗更小，那么就更新达到 j 的最小消耗和 j 的前驱节点。

DFS 搜寻：

咱们从起点开始搜寻，每次递归就拜访该节点，晓得遇到终点，达到递归边界，shortest 保留以后搜寻的最短门路，遍历以后门路上的每一条边，累加所有的边权取得总消耗，如果 total_cost==c[D]阐明以后的是最优的，应用 result 保留最优门路，最初得将入栈节点退栈并返回，递归体为拜访每一个以后节点的前驱节点，拜访结束后也得退栈回溯。

留神点：

  • 1、计算消耗的时候只需计算 n - 1 条边，并且在输入的时候得倒着拜访。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int N,M,S,D;// 顶点数，边数，终点和起点。int G[505][505];// 边权，其值示意为两点之间的间隔
int cost[505][505];// 两点之间的消耗 
bool visited[505];// 拜访标记数组
int dis[505];// 每一个城市到终点的间隔
int c[505];// 每一个城市到终点的最小消耗
vector<int> pre[505];// 保留每一个站点的前驱结点
vector<int> shortest;// 最短门路
vector<int> result;// 最优门路

void DFS(int start){shortest.push_back(start);
    if(start==S){
        // 以后结点是起点 
        int total_cost = 0;
        for(int i=shortest.size()-1;i>0;--i){total_cost += cost[shortest[i]][shortest[i-1]];
        }
        if(total_cost==c[D]){
            // 以后的门路是最优的
            result = shortest;
        }
        shortest.pop_back();
        return;
    }
    for(int i=0;i<pre[start].size();++i){DFS(pre[start][i]);
    }
    shortest.pop_back();} 

void Dijkstra(int start){
    // 初始化 
    fill(dis,dis+505,0x3fffffff);
    dis[start] = 0;
    c[start] = 0;
    // 循环 N 次
    for(int i=0;i<N;++i){
        // 首先从所有未拜访的点中找到间隔终点最小的点 
        int nearest,minDis=0x3fffffff;
        for(int j=0;j<N;++j){if(!visited[j]&&minDis>dis[j]){
                nearest = j;
                minDis = dis[j];
            }
        }
        if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 
        // 优化借助 nearest 到其余未拜访的点的间隔
        visited[nearest] = true;
        for(int j=0;j<N;++j){if(!visited[j]&&G[nearest][j]!=0){if(dis[j]>dis[nearest]+G[nearest][j]){dis[j] = dis[nearest]+G[nearest][j];
                    c[j] = c[nearest] + cost[nearest][j];
                    pre[j].clear();
                    pre[j].push_back(nearest);
                }else if(dis[j]==dis[nearest]+G[nearest][j]&&c[j]>c[nearest]+cost[nearest][j]){c[j] = c[nearest] + cost[nearest][j];
                    pre[j].push_back(nearest);
                }
            }
        }
    } 
} 

int main(){scanf("%d %d %d %d",&N,&M,&S,&D);
    int a,b,distance,C;
    for(int i=0;i<M;++i){scanf("%d %d %d %d",&a,&b,&distance,&C);
        G[b][a] = G[a][b] = distance;
        cost[b][a] = cost[a][b] = C;
    }
    Dijkstra(S);
    DFS(D);
    for(int i=result.size()-1;i>=0;--i){printf("%d",result[i]);
    }
    printf("%d %d",dis[D],c[D]);
    return 0;
}
退出移动版