1018 public bike Management (30 points)

maxmin

1018 Public Bike Management (30 branch )

The question

Give an undirected graph , Nodes are weighted , Path weight .
Find out from 0 To p The shortest path to a point , And output path ., When passing the path , If the node on the path is less than k It needs to be added to k（ give ）, Greater than k It should be reduced to k（ take ）. First from 0 Points carry x Weight , After the shortest path, the weights of nodes on the path are k, The weight of the end point is also k.
There are multiple shortest paths , Output x The smallest way ,x Also the same , Output the path with the least remaining weight .
Output
x route Residual weight

Ideas

Dijastra found all the shortest paths ,dfs Traverse all the shortest paths to find the most appropriate path .
Dijastra finds all the shortest paths ：
Generally, dijastra can find the shortest path cost , On this basis, a vector Array pre Store the previous node of each node in the shortest path （ Forerunner ）.
When the path is updated successfully , Update the precursor of this node . In this way, the path can be found through the end point .
When the new path is unsuccessful , But the updated distance is the same as the previous distance , It means that there are two points with the same distance from the point , There are two paths that are the shortest , Add a... To the precursor of this node .
adopt pre And the end point can determine all the shortest paths .

dfs Find all the shortest paths x Minimum , The path with the smallest residual weight .

Yes pre All paths can be traced back through the end point , Nodes on the path can be added to another vector Variable path1（ Save the path ）, When the starting point is added to path1 At this time path1 A complete shortest path is saved in . Traverse this path , Record this road x And residual weights . After traversing this path , Back to the next precursor of the previous node , continue …
Choose the smallest x And residual weights .

Code

#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std;
typedef struct node{
    
	int next,v;
}node;
int dis[300007],val[1007],minNeed=0x3f3f3f,minSum=0x3f3f3f;
int n;
int vis[1007];
vector<node>mp[1007];
vector<int> pre[1007],path1,path2;
void djs(int x)
{
    
	memset(dis,0x3f3f3f,sizeof(dis));// Note initialization , Pay attention to the 0 Point add in , Otherwise pre There is no starting point .
	int xmax=0x3f3f3f,temp,sum=0,a;
	dis[x]=0;
	memset(vis,0,sizeof(vis));
	while(1){
    
		temp=-1;
		xmax=0x3f3f3f;
		for(int i=0;i<=n;i++){
    
			if(vis[i]==0&&dis[i]<xmax){
    
				xmax=dis[i];
				temp=i;
			}
		}
		vis[temp]=1;
		if(temp==-1){
    
			return ;
		}
// path.push_back(temp);
		for(int i=0;i<mp[temp].size();i++){
    // Add zero point 
			a=mp[temp][i].next;
			if(vis[a]==0){
    
				if(dis[a]>dis[temp]+mp[temp][i].v){
    
					dis[a]=dis[temp]+mp[temp][i].v;
					pre[a].clear();
					pre[a].push_back(temp);
				}else if(dis[a]==dis[temp]+mp[temp][i].v){
    
					pre[a].push_back(temp);
				}
			}
		}
	}
}
void dfs(int x)	// The backtracking here is very clever , You can ponder more .
{
    
	 if(x==0){
    
	 	path1.push_back(x);
	 	int need=0,a,sum=0;
	 	for(int i=path1.size()-1;i>=0;i--){
    
	 		a=path1[i];
	 		if(val[a]>=0){
    
	 			sum+=val[a];
			}else{
    
			 	if(sum<-val[a]){
    
			 		need+=-val[a]-sum;
					sum=0;
				}else{
    
					sum+=val[a];
				}
				
			}
		 }
		 if(need<minNeed){
    
		 	minNeed=need;
		 	minSum=sum;
		 	path2=path1;
		 }else if(need==minNeed&&minSum>sum){
    
		 	minSum=sum;
		 	path2=path1;
		 }
		 path1.pop_back();
		 return;		// Notice the return
	}
	path1.push_back(x);	// Notice the two here pop——back（）
	for(int i=0;i<pre[x].size();i++){
    
		dfs(pre[x][i]);
	}
	path1.pop_back();
}
int main()
{
    
	int big,m,p,a,b,c;
	node x;
	memset(dis,0x3f3f3f,sizeof(dis));
	scanf("%d%d%d%d",&big,&n,&p,&m);
	for(int i=1;i<=n;i++){
    
		scanf("%d",&val[i]);
		val[i]-=big/2;
	}
	for(int i=0;i<m;i++){
    
		scanf("%d%d%d",&a,&b,&c);
		x.next=b;
		x.v=c;
		mp[a].push_back(x);
		x.next=a;
		x.v=c;
		mp[b].push_back(x);
	}
	djs(0);
	dfs(p);
	printf("%d ",minNeed);
	for(int i=path2.size()-1;i>=0;i--){
    
		printf("%d",path2[i]);
		if(i!=0){
    
			printf("->");
		}
	}
	printf(" %d\n",minSum);
	return 0;
}