pat1018机试指南题解

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXV = 510;
const int INF = 1000000000;

//n为顶点数量，m为边数，Cmax为最大容量，Sp为问题站点
//G为邻接矩阵，weight为点权，d[]记录最短距离
//minNeed记录最少携带的数目，minRemain记录最少带回的数目

int n,m,Cmax,Sp,numPath = 0,G[MAXV][MAXV],weight[MAXV];
int d[MAXV],minNeed = INF,minRemain = INF;
bool vis[MAXV] = {false};
vector<int> pre[MAXV];
vector<int> tempPath,path;//临时路径以及最优路径

void Dijkstra(int s){
    //s为起点
    fill(d,d+MAXV,INF);
    d[s] = 0;
    for(int i = 0;i <= n;i++){
        //循环n+1次
        int u = -1,MIN = INF; 
        for(int j = 0;j<=n;j++){
            if(vis[j]==false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        } 
        //找不到小于INF的d[u]，说明剩下的顶点和起点s不连通 
        if(u == -1) return;
        vis[u] = true;//标记u为已访问
        for(int v = 0;v <= n;v++){
            //如果v未访问&&u能到达v
            if(vis[v] == false&&G[u][v]!=INF){
                if(d[u]+G[u][v]<d[v]){
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u] + G[u][v] == d[v]){
                    pre[v].push_back(u);
                }
            } 
        } 
    } 
} 

void DFS(int v){
    if(v==0){
        //递归边界，叶子节点
        tempPath.push_back(v);
        
        int need = 0,remain = 0;
        for(int i = tempPath.size() - 1;i >= 0;i--){
            //此处必须倒着枚举
            int id = tempPath[i];//当前节点编号为id
            if(weight[id]>0){
                //点权大于0，说明要带走一部分自行车
                remain += weight[id];//当前自行车持有量增加weight[id] 
            } else{
                if(remain>abs(weight[id])){
                    //当前持有量足够补给
                    remain -= abs(weight[id]); 
                }else{
                    need+=abs(weight[id]) - remain;//不够的部分从pmbc携带
                    remain = 0;//当前持有的自行车全部用来补给 
                }
            }
        } 
        
        if(need<minNeed){//需要从PMBC携带的自行车数目更少
            minNeed = need;//优化minNeed
            minRemain = remain;//覆盖minRemain
            path = tempPath;//覆盖最优路径path 
             
        } else if(need == minNeed && remain < minRemain){
            //携带数目相同，带回数目更少
            minRemain = remain;//优化minRemain
            path = tempPath; 
        } 
        
        tempPath.pop_back();
        return;
    }
    
    tempPath.push_back(v);
    for(int i = 0;i < pre[v].size();i++){
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}

int main(){
    
    scanf("%d%d%d%d",&Cmax,&n,&Sp,&m);
    int u,v;
    fill(G[0],G[0]+MAXV*MAXV,INF);
    for(int i = 1;i <= n;i++){
        scanf("%d",&weight[i]);
        weight[i] -= Cmax/2;
    }
    
    for(int i = 0;i < m;i++){
        scanf("%d%d",&u,&v);
        scanf("%d",&G[u][v]);
        G[v][u] = G[u][v];
    }
    Dijkstra(0);
    DFS(Sp);
    printf("%d ",minNeed);
    for(int i = path.size() - 1;i >= 0;i--){
        printf("%d",path[i]);
        if(i>0) printf("->");
    }
    
    printf(" %d",minRemain);
    return 0;
}