L3-011 直捣黄龙

dijkstra+判断。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int edges[210][210],visited[210];
int cnt[210],enemy[210],pre[210],path[210];//累计城镇 累计歼敌 前驱结点 多少条路
int dist[210];//dist[i] 从起点到达i最短的距离
map<string,int> mp;//地点 序号 
string pname[210];//地点名称 
int person[210];
void dijkstra(int dist[],int visited[],int n,int s) {
	dist[s]=0;
	path[s]=1;
	for(int i=0; i<n; i++) {
		int minv = inf,minx;
		for(int j=0; j<n; j++) {
			if(!visited[j] && dist[j]<minv) {
				minv = dist[j];
				minx = j;
			}
		}
		visited[minx]=1;
		for(int j=0; j<n; j++) {
			if(minv+edges[minx][j]<dist[j]) {
				path[j]=path[minx];
				pre[j]=minx;
				dist[j]=minv+edges[minx][j];
				cnt[j]=cnt[minx]+1;
				enemy[j]=enemy[minx]+person[j];
			} else if(minv+edges[minx][j]==dist[j]) {
				path[j]+=path[minx];
				if(cnt[j]<cnt[minx]+1) {//比较城镇数量
					pre[j]=minx;
					cnt[j]=cnt[minx]+1;
					enemy[j]=enemy[minx]+person[j];
				} else if(cnt[j]==cnt[minx]+1) {
					if(enemy[j]<enemy[minx]+person[j]) {
						pre[j]=minx;
						enemy[j]=enemy[minx]+person[j];
					}
				}
			}
		}
	}
}
int main() {
	memset(edges,0x3f,sizeof(edges));
	memset(dist,0x3f,sizeof(dist));
	memset(pre,-1,sizeof(pre));
	int n,k;
	string start,ed;
	cin>>n>>k>>start>>ed;
	int s,e;
	string t;
	int count;
	s=0;//起点是0
	mp[start]=0;
	pname[0]=start;
	for(int i=1; i<n; i++) {
		cin>>t>>count;
		if(t==ed) {
			e=i;
		}
		person[i]=count;
		mp[t]=i;
		pname[i]=t;
	}
	while(k--) {
		string t1,t2;
		int dis;
		cin>>t1>>t2>>dis;
		edges[mp[t1]][mp[t2]]=edges[mp[t2]][mp[t1]]=dis;
	}
	dijkstra(dist,visited,n,s);
	vector<int> route;
	int tmp = e;
	route.push_back(tmp);
	while(pre[tmp]!=-1){
		route.push_back(pre[tmp]);
		tmp = pre[tmp];
	}
	int flag = 0;
	for(int i=route.size()-1;i>=0;i--){
		if(flag) cout << "->";
		cout << pname[route[i]];
		flag++;
	}
	cout << '\n';
	cout << path[e] << " " << dist[e] << " " << enemy[e];
	return 0;
}