1030 travel plan (30 points)

maxmin

1030 Travel Plan (30 branch )

The question

Give an undirected graph , Find the shortest path . Multiple shortest paths output the least expensive .

Ideas

Find all the shortest paths ,dfs Find the least expensive .
It's similar to this **1018 Public Bike Management (30 branch )**

Code

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
typedef struct node{
    
	int next,dis,v;
}node;
vector<node>mp[507];
vector<int> pre[507],path1,path2;
int vis[507],dis[507],minCost=0x3f3f3f,todis=0,mcost[507][507];
int n,m,s,d;
void djs(int x)
{
    
	sizeof(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f,sizeof(dis));
	dis[x]=0;
	while(1){
    
		int xmin=0x3f3f3f,temp=-1;
		for(int i=0;i<n;i++){
    
			if(vis[i]==0&&dis[i]<xmin){
    
				xmin=dis[i];
				temp=i;
			}
		}
		if(temp==-1){
    
			return ;
		}
		vis[temp]=1;
		for(int i=0;i<mp[temp].size();i++){
    
			int a=mp[temp][i].next;
			if(vis[a]==0&&mp[temp][i].dis!=0x3f3f3f){
    
				if(dis[a]>dis[temp]+mp[temp][i].dis){
    
					dis[a]=dis[temp]+mp[temp][i].dis;
					pre[a].clear();
					pre[a].push_back(temp);
				}else if(dis[a]==dis[temp]+mp[temp][i].dis){
    
					pre[a].push_back(temp);
				}
			}
		}
	}
}
void dfs(int x)
{
    
	if(x==s){
    
		path1.push_back(x);
		int cost=0;
		for(int i=path1.size()-1;i>0;i--){
    
			int p=path1[i];
			int q=path1[i-1];
			cost+=mcost[p][q];
		}
		if(cost<minCost){
    
			minCost=cost;
			path2=path1;
		}
		path1.pop_back();
		return;	// Notice the retuan, Don't forget .
	}
	path1.push_back(x);
	for(int i=0;i<pre[x].size();i++){
    
		dfs(pre[x][i]);
	}
	path1.pop_back();
}
int main()
{
    
	node x;
	int a,b,dis1,v;
	scanf("%d%d%d%d",&n,&m,&s,&d);
	for(int i=0;i<m;i++){
    
		scanf("%d%d%d%d",&a,&b,&dis1,&v);
		x.next=b;
		x.dis=dis1;
		mcost[a][b]=v;
		mcost[b][a]=v;
		x.v=v;
		mp[a].push_back(x);
		x.next=a;
		x.dis=dis1;
		x.v=v;
		mp[b].push_back(x);
	}
	djs(s);
	dfs(d);
	for(int i=path2.size()-1;i>=0;i--){
    
		printf("%d ",path2[i]);
	}
	printf("%d ",dis[d]);
	printf("%d\n",minCost);
	return 0;
}