PAT A1018 Public Bike Management（Dijkstra + DFS)

1018 Public Bike Management

分数 30

作者 CHEN, Yue

单位 浙江大学

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

The above figure illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3​, we have 2 different shortest paths:

1. PBMC -> S1​ -> S3​. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1​ and then take 5 bikes to S3​, so that both stations will be in perfect conditions.

2. PBMC -> S2​ -> S3​. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax​ (≤100), always an even number, is the maximum capacity of each station; N (≤500), the total number of stations; Sp​, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci​ (i=1,⋯,N) where each Ci​ is the current number of bikes at Si​ respectively. Then M lines follow, each contains 3 numbers: Si​, Sj​, and Tij​ which describe the time Tij​ taken to move betwen stations Si​ and Sj​. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0−>S1​−>⋯−>Sp​. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp​ is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge's data guarantee that such a path is unique.

Sample Input:

10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1

Sample Output:

3 0->2->3 0

 /**
 * 很显然的最短路径问题，但是如果只用Dijkstra算法来求解，非常的复杂，用Dijkstra +
 * DFS 简便许多，因为这要考虑起点的派送情况和终点的收集情况，只有把路径确定下来了，
 * 才能计算应该派送多少辆自行车给各个自行车站点。经过这个问题，才知道Dijkstta + DFS
 * 的强大，以前做的最短路问题，或许都还可以只用Dijksta算法来求解（各个标尺信息（最
 * 小距离，点权之和，边权之和，最短路径条数）直接在里面更新，但这个题明显很
 * 麻烦。所以以后遇到有大于等于三个标尺的最短路径问题就用Dijkstra + DFS求解吧。
 *
 * 该题的题意是：如果有多条最短路径，将选择需要从PBMC发送的自行车数量最少的路径。
 * 如果这样的路径不是唯一的，请输出需要最少自行车数量的路径，我们必须将其带回PBMC。
 * 先满足最短路径，如果最短路径相等，先满足派出去的车辆数量最少，如果派出去的车辆
 * 数量相等，选择收回的车辆最少的路径。
 *
 * 那么我们需要距离数组，路径数组，派出去的车辆信息，收回的车辆信息，共四个标尺。
 *
*/

朴素版Dijkstra算法 + DFS

/**
 * 很显然的最短路径问题，但是如果只用Dijkstra算法来求解，非常的复杂，用Dijkstra +
 * DFS 简便许多，因为这要考虑起点的派送情况和终点的收集情况，只有把路径确定下来了，
 * 才能计算应该派送多少辆自行车给各个自行车站点。经过这个问题，才知道Dijkstta + DFS
 * 的强大，以前做的最短路问题，或许都还可以只用Dijksta算法来求解（各个标尺信息（最
 * 小距离，点权之和，边权之和，最短路径条数）直接在里面更新，但这个题明显很
 * 麻烦。所以以后遇到有大于等于三个标尺的最短路径问题就用Dijkstra + DFS求解吧。
 * 
 * 该题的题意是：如果有多条最短路径，将选择需要从PBMC发送的自行车数量最少的路径。
 * 如果这样的路径不是唯一的，请输出需要最少自行车数量的路径，我们必须将其带回PBMC。
 * 先满足最短路径，如果最短路径相等，先满足派出去的车辆数量最少，如果派出去的车辆
 * 数量相等，选择收回的车辆最少的路径。
 * 
 * 那么我们需要距离数组，路径数组，派出去的车辆信息，收回的车辆信息，共四个标尺。
 * 
*/
 
 
 
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int N = 510, INF = 1e9;
int g[N][N]; //地图
int d[N], c[N]; //距离，点权
bool hs[N];
 
//pre存储各个顶点的前缀顶点，path存储最终的路径，temppath存储临时路径
vector<int> temppath, path, pre[N]; 
//Minsent派出去的车辆，Minback收回的车辆
int Minsent = INF, Minback = INF;
//顶点数，边数，终点，容量
int Nv, Ne, ed, cap;
 
void Read()
{
    fill(*g, *g + N*N, INF);
    cin >> cap >> Nv >> ed >> Ne;
    
    for(int i=1; i<=Nv; ++i)
        cin >> c[i];
        
    while(Ne--)
    {
        int u, v, t;
        cin >> u >> v >> t;
        g[u][v] = g[v][u] = t;
    }
}
 
void Dijkstra(int st)
{
    fill(d, d+N, INF);
    d[st] = 0;
    
    for(int i=0; i<Nv; ++i)
    {
        int u = -1, MIN = INF;
        for(int j=0; j<=Nv; ++j)
            if(hs[j] == 0 && d[j] < MIN)
            {
                MIN = d[j];
                u = j;
            }
            
        if(u == -1)
            return;
        hs[u] = 1;
        for(int v = 0; v<=Nv; ++v)
        {
            if(g[u][v] != INF && d[u] + g[u][v] < d[v])
            {
                d[v] = d[u] + g[u][v];
                pre[v].clear();
                pre[v].push_back(u); 
            }
            else if(g[u][v] != INF && d[u] + g[u][v] == d[v])
                pre[v].push_back(u);
        }
    }
}
 
void DFS(int v)
{
    if(v == 0)
    {
        temppath.push_back(v);
        int sent = 0, back = 0;
        
        //注意这必须从从起点开始模拟，但是path又是从终点开始存储的路径顶点，
        //所以i需要从temppath.size() - 2开始枚举，顶点0是不能算在里面的
        for(int i=temppath.size()-2; i>=0; --i)
        {
            int u = temppath[i];
            if(c[u] < cap/2)
            {
                if(back >= cap/2 - c[u])
                    back -= cap/2 - c[u];
                else 
                {
                    sent += cap/2 - c[u] - back;
                    back = 0;
                }
            }
            else
                back += c[u] - cap/2;
        }
        
        if(sent < Minsent)
        {
            path = temppath;
            Minsent = sent;
            Minback = back;
        }
        else if(sent == Minsent && back < Minback)
        {
            path = temppath;
            Minsent = sent;
            Minback = back;
        }
        
        temppath.pop_back();
        return ;
    }
    
    temppath.push_back(v);
    for(int i=0; i<pre[v].size(); ++i)
    {
        int u = pre[v][i];
        DFS(u);
    }
    temppath.pop_back();
}
 
void Print()
{
    cout << Minsent << ' ';
    for(int i=path.size()-1; i>=0; --i)
    {
        if(i != path.size() - 1)
            cout << "->";
        cout << path[i];
    }
    
    cout << ' ' << Minback << endl;
}
 
int main()
{
    Read();
    
    Dijkstra(0);
    
    DFS(ed);
    
    Print();
    
    return 0;
}

堆优化版Dijkstra + DFS:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
typedef pair<int, int> PII;
 
struct Node
{
    int v, t;
};
 
const int N = 510, INF = 1e9;
vector<Node> Adj[N];
vector<int> temppath, path;
vector<int> pre[N];
int d[N], c[N];
bool hs[N];
int Nv, Ne, ed, cap;
int maxsent = INF, maxback = INF;
 
void Read()
{
    cin >> cap >> Nv >> ed >> Ne;
    
    for(int i=1; i<=Nv; ++i)
        cin >> c[i];
        
    for(int i=0; i<Ne; ++i)
    {
        int u, v, t;
        cin >> u >> v >> t;
        Adj[u].push_back({v, t});
        Adj[v].push_back({u, t});
    }
}
 
void Dijkstra(int st)
{
    fill(d, d+N, INF);
    d[st] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, st});
    hs[0] = 1;
    
    int flag = 1;
    while(pq.size())
    {
        PII t = pq.top();
        pq.pop();
        
        int u = t.second;
        for(int i=0; i<Adj[u].size(); ++i)
        {
            int v = Adj[u][i].v;
            int w = Adj[u][i].t;
 
            if(d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                pre[v].clear();
                pre[v].push_back(u);
                
                if(hs[v] == 0)
                {
                    pq.push({d[v], v});
                    hs[v] = 1;
                }
            }
            else if(d[u] + w == d[v])
                pre[v].push_back(u);
        }
    }
}
 
void DFS(int u)
{
    if(u == 0)
    {
        temppath.push_back(u);
        
        int ans = 0, sent = 0, back = 0;
        for(int i=temppath.size()-2; i>=0; --i)
        {
            int sc = temppath[i];
            if(c[sc] < cap/2)
            {
                if(back >= cap/2 - c[sc])
                    back -= cap/2 - c[sc];
                else
                {
                    sent += cap/2 - c[sc] - back;
                    back = 0;
                }
            }
            else
                back += c[sc] - cap/2;
        }
        if(sent < maxsent)
        {
            path = temppath;
            maxsent = sent;
            maxback = back;
        }
        else if(sent == maxsent && back < maxback)
        {
            path = temppath;
            maxsent = sent;
            maxback = back;
        }
        temppath.pop_back();
        return; 
    }
    
    temppath.push_back(u);
    for(int i=0; i<pre[u].size(); ++i)
    {
        int v = pre[u][i];
        DFS(v);
    }
    temppath.pop_back();
}
 
void Print()
{
    cout << maxsent;
    
    for(auto rit = path.rbegin(); rit != path.rend(); ++rit)
    {
        if(rit != path.rbegin())
            cout << "->";
        else
            cout << ' ';
        cout << *rit;
    }
        
    cout << ' ' << maxback << endl;
}
 
int main()
{
    Read();
    
    Dijkstra(0);
    
    DFS(ed);
    
    Print();
    
    return 0;
}