PAT甲级1018.

目录

A1018

题目

样例

输入:

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

输出:

3 0->2->3 0

思路和坑点

　　Dijkstra+DFS计算出最短路径，然后根据要求进行优化.
　　最短路径的算法可以使用模板，根据另外的尺度进行优化比较复杂。但是实际比较好处理，对于获得的一条临时最短路径，做以下分析。假设从管理站0出发的时候不带自行车，也就是携带量bring=0，然后每次经过一个站，如果需要补充就减去，如果需要回收就做加上，那么整个路径上bring最小的时候的绝对值便是需要的自行车数量，如果都是回收的，最后bring依然是0，也就是不用带自行车。最后考虑待带回的自行车，遍历路径的时候计算路径上的总共自行车cnt，最后带上出发时候的自行车就是总共最后剩余的。根据这两个优化尺度获得最终的结果。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 505
#define INF 0x3fffffff
int G[MAXN][MAXN];                    //图 
bool vis[MAXN]={false};                //遍历标记 
int dis[MAXN];                        //距离数组 
int c,n,sp,m;                         
int biken[MAXN]={INF};                //每个站点的自行车数量，0号站记为无穷大，其实用不到，但是为了避免误用，这样初始化易于发现错误 
vector<int> path,temppath;            //路径数组和前驱数组 
vector<int> pre[MAXN];
int op1=INF,op2=INF;                //第二和第三尺度优化
void D(){                            //dijkstra算法模板 
    fill(dis,dis+MAXN,INF);
    dis[0]=0;
    for(int i=0;i<n+1;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n+1;j++){
            if(vis[j]==false&&dis[j]<MIN){
                u=j;
                MIN=dis[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<=n+1;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(dis[u]+G[u][v]<dis[v]){
                    dis[v]=dis[u]+G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if(dis[u]+G[u][v]==dis[v])
                    pre[v].push_back(u);
            }
        }
    }
}
void dfs(int u){                    //对获得的每一条路径进行dfs方式遍历 
    if(u==0){                        //得到一条路径时进行优化 （dfs边界） 
        int bring=0,cnt=0;            //临时的优化变量 
        for(int i=temppath.size()-1;i>=0;i--){
            cnt+=biken[temppath[i]]-c/2;
            bring=min(bring,cnt);
        }
        bring=bring>=0?0:-bring;    //计算需要带的自行车 
        cnt+=bring;                    //需要带回的自行车 
        if(bring<op1){                //如果更优，则保存更优结果 
            path=temppath;
            op1=bring; op2=cnt;
        }
        else if(bring==op1&&cnt<op2){
            path=temppath;
            op2=cnt;
        }
        return;
    }
    temppath.push_back(u);            //dfs模板 
    for(int i=0;i<pre[u].size();i++){
        dfs(pre[u][i]);
    }
    temppath.pop_back();
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    fill(G[0],G[0]+MAXN*MAXN,INF);
    scanf("%d%d%d%d",&c,&n,&sp,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&biken[i]);
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        G[a][b]=G[b][a]=c;
    }
    D();
    dfs(sp);
    printf("%d 0",op1);                //输出最终结果 
    for(int i=path.size()-1;i>=0;i--){
        printf("->%d",path[i]);
    }
    printf(" %d",op2);
    return 0;
}