【PAT】甲级1018 - Public Bike Management（最短路 & dfs & 递归 & 好题）

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
int full,n,target,m;
int num[505];       //多余的车子数 
struct Edge
{
    int to;
    int time;
};
vector<Edge> edge[505];     //存边 
vector<int> father[505];        //记录祖先 
struct Vertex
{
    int pos;
    int time;
    bool friend operator < (Vertex a,Vertex b)
    {
        return a.time > b.time;
    }
}pr,ne;
void dijkstra()
{
    int time[505];
    CLR(time,INF);
    bool vis[505] = {false};
    priority_queue<Vertex> Q;
    pr.pos = 0;
    pr.time = 0;
    Q.push(pr);
    while (!Q.empty())
    {
        pr = Q.top();
        Q.pop();
        if (pr.pos == target)
            break;
        vis[pr.pos] = true;
        for (int i = 0 ; i < edge[pr.pos].size() ; i++)
        {
            ne.pos = edge[pr.pos][i].to;
            if (vis[ne.pos])
                continue;
            ne.time = pr.time + edge[pr.pos][i].time;
            if (ne.time < time[ne.pos])     //时间更短就更新，并加入优先队列 
            {
                time[ne.pos] = ne.time;
                father[ne.pos].clear();
                father[ne.pos].push_back(pr.pos);
                Q.push(ne);
            }
            else if (ne.time == time[ne.pos])       //时间一样就加入祖先
            {
                father[ne.pos].push_back(pr.pos);
            }
        }
    }
}
int ansSend = INF;
int ansReturn = INF;
queue<int> BestRoad;        //记录最优路径 
bool check(const int Send,const int Return)     //判断是否为更优解 
{
    if (Send < ansSend)
        return true;
    else if (Send == ansSend)
        return Return < ansReturn;
    return false;
}
bool dfs(const int pos,const int Send,const int Return)     //搜索最优解 
{
    if (pos == 0)
    {
        if (check(Send,Return))
        {
            while (!BestRoad.empty())
                BestRoad.pop();
            ansSend = Send;
            ansReturn = Return;
            return true;
        }
        return false;
    }
    bool isNewAns = false;
    for (int i = 0 ; i < father[pos].size() ; i++)
    {
        int p = father[pos][i];
        //下面这句对于参数的计算是核心，太重要啊！！！！ 
        bool flag = dfs(p,num[p] > 0 ? max(Send-num[p],0) : Send - num[p] , num[p] > 0 ? (Send>num[p] ? Return : Return+(num[p]-Send)) : Return);

        if (flag)
        {
            isNewAns = true;
            BestRoad.push(pos);
        }
    }
    return isNewAns;
}
int main()
{
    scanf ("%d%d%d%d",&full,&n,&target,&m);
    full >>= 1;
    for (int i = 1 ; i <= n ; i++)
    {
        scanf ("%d",&num[i]);
        num[i] -= full;
    }
    for (int i = 1 ; i <= m ; i++)
    {
        Edge p;
        int x,y,z;
        scanf ("%d%d%d",&x,&y,&z);
        p.time = z;
        p.to = y;
        edge[x].push_back(p);
        p.to = x;
        edge[y].push_back(p);
    }
    dijkstra();     //先搜出所有最短路 
    for (int i = 1 ; i <= n ; i++)
        sort(father[i].begin(),father[i].end());
    dfs(target,max(0,-num[target]),max(num[target],0));
    cout << ansSend << " 0";
    while (!BestRoad.empty())
    {
        cout << "->" << BestRoad.front();
        BestRoad.pop();
    }
    cout << " " << ansReturn << endl;
    return 0;
}

/*
//这组数据需要考虑到车子不能再运回去的情况 
10 5 5 8
2 9 5 10 5
0 1 1
0 2 2
1 3 2
2 3 1
1 4 3
3 4 1
3 5 3
4 5 1

10 5 5 8
2 9 5 5 5
0 1 1
0 2 2
1 3 2
2 3 1
1 4 3
3 4 1
3 5 3
4 5 1

*/