注意这里和之前的诸如《All Roads Lead to Rome》这样的题目不一样，虽然都是多关键字的最短路问题，但是本题的另外两个关键字即开始从PBMC发送的车的数量send，以及最终从问题站台带回的车的数量bring，它们不像之前问题的关键字那样在Dijkstra算法中可以直接判断是否是最优值的【比如拿最短路的距离dist来说，只要dist[j]>dist[t]+d[t][j],我们就可以从t走到j】，但是拿send来说，最终决定的要发送的车的数量是走完整条路之后决定的，没办法说从a点走到b点的时候就可以决定要发送的send的数量,也就不可以决定到底是从a走b还是从a走c。

因此对于本题，我们的做法是首先用Dijkstra算法求得最短路，然后再dfs一下，求得在这些最短中最小的send和bring的最短路。

代码

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

const int N = 510,INF = 0x3f3f3f3f;
int d[N][N];
int dist[N],cpa[N];
bool st[N];
int C,n,S,m;
/*Dijkstra模板*/
void dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;//注意这里是从终点往起点做
    for(int i=0;i<=n;i++){
        int t=-1;
        for(int j=0;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
        st[t]=true;
        for(int j=0;j<=n;j++){
            if(dist[j]>dist[t]+d[t][j])
                dist[j]=dist[t]+d[t][j];
        }
    }
}
int send=INF,bring=INF;
vector<int> path,v;
//s记录的是当前一路走来多余的车和缺少的车的数量之和，当某站点缺少车辆的时候减去相关车辆，
//多余的时候加上相关的车辆，因此当s为负时代表的是走这条路径缺少了这么多辆车，当s为正代表
//多余了这么多辆车;
//mins即代表的是PBMC需要补充的车辆，它的值等于沿路走来时最小的s，因为沿路上
//所有的站点都要达到理想状态的话，那么你到了某个站点它缺多少bike就要补多少。
//注意这里的s算的是累加的和，它象征的是你到达某个点为止
//时你需要补足的自行车数量，而假如它过了这个点之后s变大了，那么就代表有站点有多余的，那么你可以利用
//这些多余的车来进行补足，因此只要保证最小的mins可以补足，那么从mins之后就可以拿别的站点多的bike了
void dfs(int u,int s,int mins){
    if(u){//只有当u不是0点即不是PBMC的时候才计算携带的bike数量
        s-=C/2-cpa[u];//当站点的车辆<C/2时减去相应的车辆，当>C/2时加上相应的车辆
        mins=min(mins,s);
    }
    if(u==S){
        int sd=abs(min(mins,0));//mins为正代表的是多余了这么多自行车，所以不要携带任何自行车
        int bg=sd+s;//需要带回的自行车等于多余的自行车(为负数代表到S时还缺少多少自行车)+开始带来的自行车之和
        if(send>sd){
            path=v;send=sd;bring=bg;
        }else if(send==sd&&bring>bg){
            path=v;bring=bg;
        }
        return;
    }
    for(int i=1;i<=n;i++){
        //注意Dijkstra算法是从终点往起点做的；
        //所以这里判断的方向相当于是某个点走到起点的方向
        if(dist[u]==dist[i]+d[u][i]){//如果走i结点可能是最短路的话
            v.push_back(i);
            dfs(i,s,mins);
            v.pop_back();
        }
    }
}

int main(){
    cin>>C>>n>>S>>m;
    for(int i=1;i<=n;i++) scanf("%d",&cpa[i]);
    memset(d,0x3f,sizeof d);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b]=d[b][a]=min(d[a][b],c);
    }
    dijkstra();


    //从PBMC开始走,在PMBC不需要计算s和mins
    dfs(0,0,0);
    cout<<send<<" "<<0;
    for(int i=0;i<path.size();i++) cout<<"->"<<path[i];
    cout<<" "<<bring;
    return 0;
}