Public Bike Management

#include<bits/stdc++.h>
using namespace std;

const int Max=510;
const int INF=INT_MAX;
int c,n,sp,m;
int dis[Max],weight[Max],minNeed=INF,minRemain=INF;
int G[Max][Max];
bool visit[Max];
vector<int> pre[Max];
vector<int> path,temp;

void Dijistra() {
	fill(dis,dis+Max,INF);
	dis[0]=0;
	for(int i=0; i<n; i++) {
		int u=-1,Min=INF;
		for(int j=0; j<=n; j++) {
			if(dis[j]<Min&&!visit[j]) {
				Min=dis[j];
				u=j;
			}
		}
		if(u==-1) return ;
		visit[u]=1;
		for(int v=0; v<=n; v++) {
			if(!visit[v]&&G[u][v]!=INF) {
				if(dis[v]>dis[u]+G[u][v]) {
					dis[v]=dis[u]+G[u][v];
					pre[v].clear();
					pre[v].push_back(u);
				} else if(dis[v]==dis[u]+G[u][v]) {
					pre[v].push_back(u);
				}
			}
		}
	}
}

void DFS(int v) {
	if(v==0) {
		temp.push_back(v);
		int need=0,remind=0;
		for(int i=temp.size()-1; i>=0; i--) {
			int id=temp[i];
			if(weight[id]>0) {
				remind+=weight[id];
			} else {
				if(remind>abs(weight[id]) ) {
					remind+=weight[id];
				} else {
					need+=abs(weight[id])-remind;
					remind=0;
				}
			}
		}
		if(need<minNeed) {
			minNeed=need;
			minRemain=remind;
			path=temp;
		} else if(need==minNeed&&remind<minRemain) {
			minRemain=remind;
			path=temp;
		}
		temp.pop_back();
		return ;
	}
	temp.push_back(v);
	for(int i=0;i<pre[v].size();i++){
		DFS(pre[v][i]);
	}
	temp.pop_back();
}

int main() {
	scanf("%d %d %d %d",&c,&n,&sp,&m);
	for(int i=1; i<=n; i++) {
		scanf("%d",&weight[i]);
		weight[i]-=c/2;
	}
	int from,to;
	fill(G[0],G[0]+Max*Max,INF);
	for(int i=0; i<m; i++) {
		scanf("%d %d",&from,&to);
		scanf("%d",&G[from][to]);
		G[to][from]=G[from][to];
	}
	Dijistra();
	DFS(sp);
	printf("%d ",minNeed);
	int k=path.size();
	for(int i=k-1; i>=0; i--) {
		printf("%d",path[i]);
		if(i>0) printf("->");
	}
	printf(" %d\n",minRemain);
	return 0;
}