L3-011 direct attack Huanglong (30 points)

Portal

This is a war movie —— You need to start from your own base , All the way to the enemy's base camp . First of all, time is life , So you have to choose the right path , Capture the enemy base camp as quickly as possible . When such a path is not unique , It is required to choose the path that can liberate the most towns along the way . If such a path is not unique , Then select the path that can effectively kill the most enemy .

Input format ：

The first line of input is given 2 A positive integer N（2 ≤ N ≤ 200, Total number of towns ） and K（ Number of roads between cities and towns ）, And the codes of your base camp and enemy base camp . And then N-1 That's ok , Each line gives the code of a town other than your base camp and the number of enemy troops stationed , Separated by spaces . Then there is K That's ok , Each line is formatted Cities and towns 1 Cities and towns 2 distance Give the length of the road between two towns . There are every town here （ Including the bases of both sides ） The code name is by 3 A string of uppercase letters .

Output format ：

Find the most suitable attack path according to the requirements of the topic （ The title guarantees the fastest speed 、 Liberation most 、 The strongest path to kill is the only ）, And in the first line according to the format Your base camp -> Cities and towns 1->...-> Enemy stronghold Output . The second line sequentially outputs the number of fastest attack paths 、 The shortest attack distance 、 The total number of enemy annihilations , In the meantime 1 Space separation , There must be no extra space at the beginning and end of the line .

sample input ：

10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10

sample output ：

PAT->PTA->PDS->DBY
3 30 210

  Graph topics with strong comprehensiveness , The characteristics of this solution are as follows

1. Use two map As a hash table

2. Initialize all nodes to the maximum distance , Make it available as an access array

3. not used Djkstra Algorithm , It's queue access , Each time the data is refreshed, the node is re queued , Or you won't join the team anymore

#include <bits/stdc++.h>
using namespace std;
int main(void){
	int n,k,tar,**t;
	string st,ed;
	cin>>n>>k>>st>>ed;
	map<string,int> m;														// Character to number mapping  
	map<int,string> mi;														// Number to character mapping  
	m[st]=0;
	mi[0]=st;
	int ps[n];																// Number of city defenders  
	int dis[n];fill(dis,dis+n,0x7fffffff);									// distance , The initial is the maximum  
	int path[n];															// route 
	int rs[n]={0};															// Number of paths  
	int sav[n]={0};															// Number of casualties  
	int tot[n]={0};															// Number of passing cities  
	vector<int> p[n];														// Adjacency list  
	t=(int**)malloc(sizeof(int*)*n);										// Adjacency matrix , Length of storage road  
	for(int i=0;i<n;i++){
		t[i]=(int*)malloc(sizeof(int)*n);
		for(int j=0;j<n;j++)t[i][j]=0;
	}
	for(int i=1;i<n;i++){
		string x;
		int c;
		cin>>x>>c;
		m[x]=i;
		mi[i]=x;
		ps[i]=c;
	}
	tar=m[ed];
	while(k--){
		string xt,yt;
		int d,x,y;
		cin>>xt>>yt>>d;
		x=m[xt];
		y=m[yt];
		p[x].push_back(y);
		p[y].push_back(x);
		t[x][y]=d;
		t[y][x]=d;
	}
	queue<int> f;															// Figure access queue  
	f.push(0);
	path[0]=-1;
	dis[0]=0;
	rs[0]=1; 
	while(!f.empty()){
		int x=f.front();f.pop();
		for(int i=0;i<p[x].size();i++){
			if(dis[x]+t[x][p[x][i]]<dis[p[x][i]]){							// Closer 
				dis[p[x][i]]=dis[x]+t[x][p[x][i]];							// distance  
				path[p[x][i]]=x;											// route 
				rs[p[x][i]]=rs[x];											// Number of paths  
				sav[p[x][i]]=sav[x]+ps[p[x][i]];							// Number of casualties 
				tot[p[x][i]]=tot[x]+1;										// Number of passing cities 
				f.push(p[x][i]);											// The team  
			}
			else if(dis[x]+t[x][p[x][i]]==dis[p[x][i]]){					// When the distance is equal 
				rs[p[x][i]]=0;												// The number of shortest paths must be counted again  
				for(int j=0;j<p[p[x][i]].size();j++){						// Traverse the cities with the shortest path and count  
					if(dis[p[x][i]]==dis[p[p[x][i]][j]]+t[p[x][i]][p[p[x][i]][j]])
						rs[p[x][i]]+=rs[p[p[x][i]][j]];
				} 
				if(tot[p[x][i]]<tot[x]+1){									// Fewer cities  
					path[p[x][i]]=x;										// route 
					sav[p[x][i]]=sav[x]+ps[p[x][i]];						// Number of casualties 
					tot[p[x][i]]=tot[x]+1;									// Number of passing cities 
					f.push(p[x][i]);										// The team  
				}
				else if(tot[p[x][i]]==tot[x]+1){							// When cities are equal  
					if(sav[p[x][i]]<sav[x]+ps[p[x][i]]){					// Fewer casualties  
						path[p[x][i]]=x;									// route 
						sav[p[x][i]]=sav[x]+ps[p[x][i]];					// Number of casualties 
						f.push(p[x][i]);									// The team  
					}
				} 
			} 
		}
	}
	stack<int> ot;															// Path output stack  
	int tt=tar;
	while(tt!=-1){
		ot.push(tt);
		tt=path[tt];
	}
	while(!ot.empty()){
		int as=ot.top();
		cout<<mi[as];
		ot.pop();
		if(!ot.empty())cout<<"->";
	}
	cout<<endl<<rs[tar]<<' '<<dis[tar]<<' '<<sav[tar];
	return 0;
}