Home PAT 1018 Public Bike Management
Post
Cancel

PAT 1018 Public Bike Management

Link

又是带路径回溯的 Dijkstra. 记录前驱节点即可. 要注意的是, 首先是路径最短, 其次是从 PBMC 带过去的最少, 最后是带回 PBMC 的最少.

再就是只能单向匀自行车不能双向. 即, 只能是从 PBMC 出发沿着这条路径检查各个车站, 如果有多出来的就可以匀给后面的车站, 而后面的车站多出来则不能匀给前面的车站. 因此, 需要时刻记录“带回”和“带来”这两个量, 而不能用一个量来记录.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
const int INF=0x3f3f3f3f;
int cmax,n,sp,m,curTakeBack=INF,curBringTo=INF;
int c[510],g[510][510],dis[510];
vector<int>pre[510],tempPath,ansPath;
bool vis[510];
void DFS(int x,int _takeBack,int _bringTo){
    if(x==sp){
        if(_bringTo<curBringTo||(_bringTo==curBringTo&&_takeBack<curTakeBack)){
            curTakeBack=_takeBack;
            curBringTo=_bringTo;
            ansPath=tempPath;
        }
        return;
    }
    for(int i=0;i<pre[x].size();++i){
        int takeBack=_takeBack,bringTo=_bringTo;
        tempPath.push_back(pre[x][i]);
        int tempTakeBack=c[pre[x][i]]>cmax?c[pre[x][i]]-cmax:0;
        int tempBringTo=c[pre[x][i]]<cmax?cmax-c[pre[x][i]]:0;
        if(tempBringTo>0){
            if(takeBack>=tempBringTo){
                takeBack-=tempBringTo;
                tempBringTo=0;
            }else{
                tempBringTo-=takeBack;
                takeBack=0;
            }
            bringTo+=tempBringTo;
        }else takeBack+=tempTakeBack;
        DFS(pre[x][i],takeBack,bringTo);
        tempPath.pop_back();
    }
}
void Dijkstra(){
    dis[sp]=0;
    for(int i=0;i<=n;++i){
        int u=-1,minv=INF;
        for(int j=0;j<=n;++j)
            if(!vis[j]&&dis[j]<minv){
                u=j;
                minv=dis[j];
            }
        if(u==-1) break;
        vis[u]=true;
        for(int j=0;j<=n;++j)
            if(!vis[j]&&g[u][j]!=INF){
                if(dis[j]>g[u][j]+dis[u]){
                    pre[j].clear();
                    pre[j].push_back(u);
                    dis[j]=g[u][j]+dis[u];
                }else if(dis[j]==g[u][j]+dis[u]){
                    pre[j].push_back(u);
                }
            }
    }
    tempPath.push_back(0);
    DFS(0,0,0);
    printf("%d ",curBringTo);
    for(int i=0;i<ansPath.size();++i){
        if(i!=0) printf("->");
        printf("%d",ansPath[i]);
    }
    printf(" %d\n",curTakeBack);
}
int main() {
    memset(dis,63,sizeof(dis));
    memset(g,63,sizeof(g));
    scanf("%d%d%d%d",&cmax,&n,&sp,&m);
    cmax>>=1;
    for(int i=1;i<=n;++i)
        scanf("%d",&c[i]);
    for(int i=1;i<=m;++i){
        int s1,s2,t;
        scanf("%d%d%d",&s1,&s2,&t);
        g[s1][s2]=g[s2][s1]=t;
    }
    Dijkstra();
    return 0;
}
This post is licensed under CC BY 4.0 by the author.