PAT A1030 Travel Plan

PAT A1030 Travel Plan 

dijkstra  优先队列实现  +  dfs 

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 10000;
const int INF = 0x3f3f3f3f;


struct node{
	int to,len,cost,rec;
	node(){}
	node(int to,int len,int cost,int rec):to(to),len(len),cost(cost),rec(rec){}
};

struct qnode{
	int id,len;
	qnode(){};
	qnode(int id,int len):id(id),len(len){};
	bool operator < (const qnode & b) const{
		return len > b.len;
	}
	
};

vector<node> map_[MAXN];
void add_edge(int a,int b,int len ,int cost){
	map_[a].push_back(node(b,len,cost,map_[b].size()));
	map_[b].push_back(node(a,len,cost,map_[a].size()-1));
}

int N,M,start,end; 

int dist[MAXN];

vector<int> pre[MAXN];
void dijkstra(int start){
	
	fill(dist,dist+N,INF);
	dist[start] = 0;
	priority_queue<qnode> que;
	que.push(qnode(start,0));
	
	while(!que.empty()){
		qnode temp = que.top(); que.pop();
		for(int i=0;i<map_[temp.id].size();i++){
			node nnode = map_[temp.id][i];
			if(dist[nnode.to]> dist[temp.id] + nnode.len){
				dist[nnode.to] =  dist[temp.id] + nnode.len;
				que.push(qnode(nnode.to,dist[nnode.to]));
				pre[nnode.to].clear();
				pre[nnode.to].push_back(temp.id);
			}else if(dist[nnode.to] == dist[temp.id] + nnode.len){
				pre[nnode.to].push_back(temp.id);
			}
		}
	}	
}

int cal(vector<int> path){
	int ans =0;
	for(int i=path.size() - 1;i>=1;i--){
		for(int j=0;j<map_[path[i]].size();j++){
			if(map_[path[i]][j].to == path[i-1]){
				ans += map_[path[i]][j].cost;
				break;	
			}
		} 
	}
	return ans;
}

void output(vector<int> path){

	printf("-------------\n");
	for(int i=path.size() - 1;i>=0;i--){
		printf("%d ",path[i]);
	}
}



int min_cost = INF;
vector<int> main_path;
vector<int> temp_path;

void dfs_out(int start,int end){
	
	if(start == end){
		temp_path.push_back(start);
		int temp_cost = cal(temp_path);
//		output(temp_path);
//		printf("%d \n",temp_cost);
		if(temp_cost < min_cost){
			main_path = temp_path;
			min_cost = temp_cost;
		}
		temp_path.pop_back();
		return;
	}
	
	temp_path.push_back(end);
	for(int i=0;i<pre[end].size();i++){
		dfs_out(start,pre[end][i]);
	}
	temp_path.pop_back();
}




int main(){
	
	scanf("%d%d%d%d",&N,&M,&start,&end);
	for(int i=0;i<M;i++){
		int a,b,len,cost;
		scanf("%d%d%d%d",&a,&b,&len,&cost);
		add_edge(a,b,len,cost);
	}
//	for(int i=0;i<N;i++){
//		for(int j=0;j<map_[i].size();j++){
//			printf("%d ",map_[i][j].to);
//		}
//		printf("\n");
//	}
		
	
	dijkstra(start);
	dfs_out(start,end);
	
	for(int i=main_path.size() - 1;i>=0;i--){
		printf("%d ",main_path[i]);
	}
	printf("%d %d",main_path.size(),min_cost);
	
	return 0;
}