1003 Emergency (25 分)

方法一：暴力回溯法

// 甲级pat1003（图，未完成）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
#include<vector>
#include<map>
using namespace std;


struct target_city
{
	int id;
	int road_distance;
};
int shortest_paths_variety= 0, max_helper=0, 
initial_city, final_city,shortest_distance= 2147483647;
vector<int>helper_num;
void MyInsert(map<int, vector<target_city>>&mp, 
	int start_city, target_city tempstruct);
void find(map<int, vector<target_city>>&mp,int current_city,vector<bool>visited,
	int current_distance,int current_helper);



int main()
{
	vector<bool>visited_template;
	map<int, vector<target_city>>mp;
	//<city_id,neiboring_cities>
	int city_num, road_num;
	cin >> city_num >> road_num >> initial_city >> final_city;
	for (int i = 0; i < city_num; i++)
		visited_template.push_back(false);//initialize visited
	visited_template[initial_city] = true;
	for (int i = 0; i < city_num; i++)
	{
		int temp;
		cin >> temp;
		helper_num.push_back(temp);
	}//scan helper num

	for (int i = 1; i <= road_num; i++)
	{
		int start_city,end_city;
		target_city tempstruct;
		cin >> start_city >> end_city >> tempstruct.road_distance;
		tempstruct.id = end_city;
		MyInsert(mp, start_city, tempstruct);
		tempstruct.id = start_city;
		MyInsert(mp, end_city, tempstruct);
	}//build map
	if (city_num == 1)
	{
		cout << 1 << " " << helper_num[0] + helper_num[1];
			return 0;
	}
	//find
	find(mp,initial_city,visited_template,0,0);
	cout << shortest_paths_variety << " " << max_helper;
	system("pause");
	return 0;
}

void MyInsert(map<int, vector<target_city>>&mp, int start_city, target_city tempstruct)
{
	auto item = mp.find(start_city);
	if (item == mp.end())
	{
		vector<target_city>vec;
		vec.push_back(tempstruct);
		mp.insert(pair<int, vector<target_city>>(start_city, vec));
	}
	else
	{
		item->second.push_back(tempstruct);
	}
	return;
}



void find(map<int, vector<target_city>>&mp, int current_city, vector<bool>visited,
	int current_distance, int current_helper)
{
	/*
	mp<current_city,vector<target_city>>
	vector<target_city> <=>target_city[city_num]
	target_city<=>id,road_distance
	*/
	if (current_city == initial_city)
		current_helper += helper_num[initial_city];
	auto vec = mp[current_city];
	for (auto item = vec.begin(); item != vec.end(); item++)
	{
		if (item->id == final_city)//结束
		{
			current_distance += item->road_distance;
			current_helper += helper_num[final_city];
			if (current_distance < shortest_distance)
			{
				shortest_paths_variety = 1;
				shortest_distance = current_distance;
				max_helper = current_helper;
				return;
			}
			if (current_distance > shortest_distance)
				return;
			if (current_distance == shortest_distance)
			{
				shortest_paths_variety++;
				if (current_helper > max_helper)
					max_helper = current_helper;
				return;
			}
		}
		if (!visited[item->id])
		{
			auto visitedcpy = visited;
			visitedcpy[item->id] = true;
			//current_distance += item->road_distance;
			//current_city = item->id;
			//current_helper += helper_num[item->id];
			find(mp, item->id, visitedcpy, current_distance+ item->road_distance, current_helper+ helper_num[item->id]);
		}
	}
	return;
}

方法二：常规Dijkstra算法

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 501
#define INF 0x3f3f3f3f

int city_num,road_num,start_city,end_city;
int people[MAX],edge[MAX][MAX];

pair<int,int>Dijkastra()
{
	
	int dist[MAX],max_people[MAX],road_variety[MAX],vis[MAX];
	fill_n(dist,MAX,INF);
	fill_n(max_people,MAX,0);
	fill_n(road_variety,MAX,0);
	fill_n(vis,MAX,false);
	dist[start_city]=0;
	max_people[start_city]=people[start_city];
	road_variety[start_city]=1;
	
	
	for(int i=0;i<city_num;i++)
	{
	//	print(dist,dist+city_num);
		
		int u=-1,min_dist=INF;
		for(int v=0;v<city_num;v++)
		{
			if(!vis[v]&&dist[v]<min_dist)
			{
				u=v;
				min_dist=dist[v];
			}
		}
		vis[u]=true;
		for(int v=0;v<city_num;v++)
		{
			if(vis[v]||edge[u][v]==INF)
				continue;
			if(dist[u]+edge[u][v]<dist[v])
			{
				dist[v]=dist[u]+edge[u][v];
				road_variety[v]=road_variety[u];
				max_people[v]=max_people[u]+people[v]; 
			}
			else
			if(dist[u]+edge[u][v]==dist[v])
			{
				road_variety[v]+=road_variety[u];
				max_people[v]=max(max_people[v],max_people[u]+people[v]); 
			}
		}
	}
	return make_pair(road_variety[end_city],max_people[end_city]);
	 //output road_var and max_peo
}


int main()
{
	for(auto& c:edge)
		for(auto& d:c)
			d=INF;
	cin>>city_num>>road_num>>start_city>>end_city;
	for(int i=0;i<city_num;i++)
		cin>>people[i];
	for(int i=0;i<road_num;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		edge[a][b]=edge[b][a]=w; 
	}
	auto p=Dijkastra();
	cout<<p.first<<" "<<p.second;
	system("pause"); 
	return 0;
}

方法三：堆优化的Dijkstra算法

//方法二：堆优化的dijkast算法
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

#define MAX 501
#define INF 0x3f3f3f3f

int city_num,road_num,start_city,end_city;
int people[MAX];
int edge[MAX][MAX];
vector<int>mp[MAX];

pair<int,int> Dijkstra()
{
	int dist[MAX],max_people[MAX],road_variety[MAX],vis[MAX];
	fill_n(dist,MAX,INF);
	fill_n(max_people,MAX,0);
	fill_n(road_variety,MAX,0);
	fill_n(vis,MAX,false);
	dist[start_city]=0;
	max_people[start_city]=people[start_city];
	road_variety[start_city]=1;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>heap;
	heap.push(make_pair(0,start_city));
	int cnt=0;
	while(cnt!=city_num)
	{
		auto top=heap.top();
		heap.pop();
		int u=top.second;
		if(vis[u])
            continue;
		vis[u]=true;
        cnt++;
		for(int i=0;i<mp[u].size();i++)
		{
			int v=mp[u][i];
			if(vis[v]||edge[u][v]==INF)
			continue;
			if(dist[u]+edge[u][v]<dist[v])
			{
				dist[v]=dist[u]+edge[u][v];
				road_variety[v]=road_variety[u];
				max_people[v]=max_people[u]+people[v];
			}
			else
			if(dist[u]+edge[u][v]==dist[v])
			{
				road_variety[v]+=road_variety[u];
				max_people[v]=max(max_people[v],max_people[u]+people[v]);
			}
			heap.push(make_pair(dist[v],v));
		}
	}
	return make_pair(road_variety[end_city],max_people[end_city]);
	//output road_var and max_peo
}

int main()
{
    cin>>city_num>>road_num>>start_city>>end_city;
	for(int i=0;i<city_num;i++)
		cin>>people[i];
	for(int i=0;i<road_num;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		edge[a][b]=edge[b][a]=w;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	auto p=Dijkstra();
	cout<<p.first<<" "<<p.second;
	system("pause");
	return 0;
 }

方法四：堆优化的Dijkstra算法+动态规划

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

#define MAX 501
#define INF 0x3f3f3f3f

int city_num,road_num,start_city,end_city;
int people[MAX];
int edge[MAX][MAX];
vector<int>mp[MAX];
vector<int>pre[MAX];

int road_variety[MAX];
int max_people[MAX];
int getRoadVariety(int cur_ind)
{
    auto& res=road_variety[cur_ind];
    if(res!=-1)
        return res;
    if(cur_ind==start_city)
        return res=1;
    else
    {
        int sum=0;
        for(auto c:pre[cur_ind])
            sum+=getRoadVariety(c);
        return res=sum;
    }
}

int getMaxPeople(int cur_ind)
{
    auto&res=max_people[cur_ind];
    if(res!=-1)
        return res;
    if(cur_ind==start_city)
        return res=people[start_city];
    else
    {
        int cur_max=-1;
        for(auto c:pre[cur_ind])
            cur_max=max(cur_max,people[cur_ind]+getMaxPeople(c));
        return res=cur_max;
    }
}

pair<int,int> Dijkstra()
{
	int dist[MAX],vis[MAX];
	fill_n(dist,MAX,INF);
	fill_n(vis,MAX,false);
	dist[start_city]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>heap;
	heap.push(make_pair(0,start_city));
	int cnt=0;
	while(cnt!=city_num)
	{
		auto top=heap.top();
		heap.pop();
		int u=top.second;
		if(vis[u])
            continue;
		vis[u]=true;
        cnt++;
		for(int i=0;i<mp[u].size();i++)
		{
			int v=mp[u][i];
			if(vis[v]||edge[u][v]==INF)
			continue;
			if(dist[u]+edge[u][v]<dist[v])
			{
				dist[v]=dist[u]+edge[u][v];
				pre[v].clear();
				pre[v].push_back(u);
			}
			else
			if(dist[u]+edge[u][v]==dist[v])
			{
				pre[v].push_back(u);
			}
			heap.push(make_pair(dist[v],v));
		}
	}
	return make_pair(getRoadVariety(end_city),getMaxPeople(end_city));
}

int main()
{
    fill_n(road_variety,MAX,-1);
    fill_n(max_people,MAX,-1);
    cin>>city_num>>road_num>>start_city>>end_city;
	for(int i=0;i<city_num;i++)
		cin>>people[i];
	for(int i=0;i<road_num;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		edge[a][b]=edge[b][a]=w;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	auto p=Dijkstra();
	cout<<p.first<<" "<<p.second;
	system("pause");
	return 0;
 }

1003 Emergency (25 分)

继续阅读

PAT (Advanced Level) Practise 1065 A+B and C (64bit) (20)

PAT (Advanced Level) Practise 1033 To Fill or Not to Fill (25)

PAT (Advanced Level) Practise 1046 Shortest Distance (20)

PAT (Advanced Level) Practise 1100 Mars Numbers (20)

PAT (Advanced Level) Practise 1018 Public Bike Management (30)

PAT (Advanced Level) Practise 1024 Palindromic Number (25)

PAT (Advanced Level) Practise 1012 The Best Rank (25)

数据库连接出现Communications link failure

PAT (Top Level) Practise 1008 Airline Routes (35)

PAT (Top Level) Practise 1007 Red-black Tree (35)

HDU 3268 Columbus’s bargain

PAT刷题小结

PAT (Advanced Level) Practise 1083 List Grades (25)

HDU 4725 The Shortest Path in Nya Graph

PAT (Advanced Level) Practise 1066 Root of AVL Tree (25)

Dijkstra--简易版（最短路径）