1018 Public Bike Management (30) & 1030 Travel Plan (30)

目录

🧡1018 Public Bike Management

解析

易错点

代码

🧡1030 Travel Plan

解析

易错点

代码

---

💟这里是CS大白话专场，让枯燥的学习变得有趣！

💟没有对象不要怕，我们new一个出来，每天对ta说不尽情话！

💟好记性不如烂键盘，自己总结不如收藏别人！

💌1018和1030这两个求最短路径的题都需要用Dijkstra+DFS算法，常被PAT用做压轴题，背也要背下来！

🧡1018 Public Bike Management

题目链接：PTA | 程序设计类实验辅助教学平台

解析

💌有N个站点，站点间交通时长T，每个站点最多容纳Cmax个自行车，最优状态是放置Cmax/2辆自行车。给出问题站点Sp，求出从源点0到问题站点的最短路径，路径上的站点都要重新调整到最优状态，若有多条路径，选择需要从源点send最少自行车的路径，若不需要send，选择返回时需要带回自行车最少的路径。

易错点

🍠因为可能存在多条最短路径，所以某个站点的前一个最短路径站点可能有多个，在记录时用vector存储。在DFS中，需要计算每一条最短路径的send和back情况，一条从源点到问题站点的路径计算完成后，tempPath返回到上一次路径分叉的地方，从下一条路径继续计算。这里的递归思想很值得思考~~(*^▽^*)~~

🍠输出的时候记得倒序输出。

代码

#include 
#include 
#include 
using namespace std;
const int inf = 0x3f3f3f;
int Cmax,N,Sp,M; //Cmax:站点最大容量 N:站点数 Sp:问题站点 M:道路数
int Ci[510],T[510][510]; //每个站点自行车数量,站点间时间
int vis[510],dis[510];
vector<int> pre[510],path,tempPath;
int minSend=inf,minBack=inf;
 
//**标准最短路径算法**
void Dijkstra(int s){
    fill(dis,dis+N,inf);
    dis[s] = 0;
    while(1){
        int index = -1;
        int min_dis = inf;
        for(int i=0;i
            if(!vis[i] && dis[i] < min_dis){
                index = i;
                min_dis = dis[i];
            }
        }
        if(index == -1) return;
        vis[index] = 1;
        for(int i=0;i
            if(!vis[i] && T[index][i]){
                if(dis[index]+T[index][i]
                    dis[i] = dis[index]+T[index][i];
                    pre[i].clear();
                    pre[i].push_back(index);
                }else if(dis[index]+T[index][i]==dis[i]){
                    pre[i].push_back(index);
                }
            }
        }
    }
}
 
void DFS(int s){
    tempPath.push_back(s); //从问题节点倒着插入到源点
    //递归到源点
    if(s==0){
        int send=0,back=0;
        for(int i=tempPath.size()-1;i>-1;i--){
            //如果节点自行车数多了，则带走
            if(Ci[tempPath[i]]>0) back += Ci[tempPath[i]];
            //如果少了
            else{
                //先由从其他站点带走的补充
                if(back>-Ci[tempPath[i]]) back += Ci[tempPath[i]];
                //不够的话则增加源点带出的自行车
                else{
                    send += -Ci[tempPath[i]]-back;
                    back = 0;
                }
            }
        }
        if(send
            minSend = send;
            minBack = back;
            path = tempPath;
        }else if(send==minSend && back
            minBack = back;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    for(int i=0;isize();i++){
        DFS(pre[s][i]);
    }
    //没有多条路径则回退
    tempPath.pop_back();
}
 
int main(){
    cin >> Cmax >> N >> Sp >> M;
    N++; //加上源点
    int Si,Sj;
    fill(T[0],T[0]+N*N,0);
    for(int i=1;i
        cin >> Ci[i];
        Ci[i] -= Cmax/2; //大于0的话需要带走，小于0需要补充
    }
    for(int i=0;i
        cin >> Si >> Sj;
        cin >> T[Si][Sj];
        T[Sj][Si] = T[Si][Sj];
    }
    Dijkstra(0); //PBMC位于源点
    DFS(Sp);
    cout << minSend << " ";
    cout << path[path.size()-1];
    for(int i=path.size()-2;i>=0;i--)
    {
        cout << "->" << path[i];
    }
    cout << " " << minBack << endl;
    return 0;
}

🧡1030 Travel Plan

题目链接：PTA | 程序设计类实验辅助教学平台

解析

💌相对来说这道题就简单多啦，同样是找最短路径，如果有多条，选择花费最少的那一条。为什么这道题不需要找出所有的路径之后再计算呢？因为花费肯定是越来越多的，只需要从当前状态判断就可以了，而上一道题我们不知道后面的站点自行车是多了还是少了。

易错点

🍠经过上道题的洗礼这道题轻而易举啦~~

代码

#include 
using namespace std;
 
int N,M,S,D;
int mp[510][510],dis[510],vis[510];
int money[510][510],cost[510];
int pre[510];
vector<int>path; //不固定长度，可以调用函数
const int inf = 0x3f3f3f;
 
void DFS(int d)
{
    if(d == S)
    {
        path.push_back(d); //从起始点开始push
        return;
    }
    DFS(pre[d]); //从后往前递归
    path.push_back(d);  //一直push到终点
}
 
void Dijkstra(int s)
{
    fill(dis,dis+N,inf);
    dis[s] = 0;
    cost[s] = 0;
    while(1)
    {
        int index = -1;
        int min_dis = inf;
        //遍历所有没有访问过的节点，找出距离源点s最近的节点index
        for(int i=0; i
        {
            if(!vis[i] && dis[i] < min_dis)
            {
                index = i;
                min_dis = dis[i];
            }
        }
        if(index == -1) return;
        vis[index] = 1;
        //遍历所有与index相邻的节点，更新dis
        for(int i=0; i
        {
            if(!vis[i] && mp[index][i]) //存在路径
            {
                if(dis[index] + mp[index][i] < dis[i])
                {
                    dis[i] = dis[index] + mp[index][i];
                    cost[i] = cost[index] + money[index][i];
                    pre[i] = index; //总路程最短的前驱顶点
                }
                else if(dis[index] + mp[index][i] == dis[i])
                {
                    if(cost[index] + money[index][i] < cost[i])
                    {
                        cost[i] = cost[index] + money[index][i];
                        pre[i] = index;
                    }
                }
            }
        }
    }
}
int main(){
    cin >> N >> M >> S >> D;
    for(int i=0; i
    {
        int start,end,far,much;
        cin >> start >> end >> far >> much;
        mp[start][end] = mp[end][start] = far; //距离
        money[start][end] = money[end][start] = much; //花费
    }
    Dijkstra(S);
    DFS(D);
    for(int i=0; isize(); i++)
    {
        cout << path[i] << " ";
    }
    cout << dis[D] << " " << cost[D] << endl;
}