L3-011 直搗黃龍 （最短路徑）

本題是一部戰争大片 —— 你需要從己方大學營出發，一路攻城略地殺到敵方大學營。首先時間就是生命，是以你必須選擇合适的路徑，以最快的速度占領敵方大學營。當這樣的路徑不唯一時，要求選擇可以沿途解放最多城鎮的路徑。若這樣的路徑也不唯一，則選擇可以有效殺傷最多敵軍的路徑。

輸入格式：

輸入第一行給出 2 個正整數 N（2 ≤ N ≤ 200，城鎮總數）和 K（城鎮間道路條數），以及己方大學營和敵方大學營的代号。随後 N-1 行，每行給出除了己方大學營外的一個城鎮的代号和駐守的敵軍數量，其間以空格分隔。再後面有 K 行，每行按格式

城鎮1 城鎮2 距離

給出兩個城鎮之間道路的長度。這裡設每個城鎮（包括雙方大學營）的代号是由 3 個大寫英文字母組成的字元串。

輸出格式：

按照題目要求找到最合适的進攻路徑（題目保證速度最快、解放最多、殺傷最強的路徑是唯一的），并在第一行按照格式

己方大學營->城鎮1->...->敵方大學營

輸出。第二行順序輸出最快進攻路徑的條數、最短進攻距離、殲敵總數，其間以 1 個空格分隔，行首尾不得有多餘空格。

輸入樣例：

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
           

輸出樣例：

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

解題思路

把起點編号為1，之後的點按照給出順序編号為2~n。用map存string對應的int編号。用數組存int編号對應的string名字。然後建圖，記終點編号為t。找最短路，記錄到每個節點的最短路徑，以及在保證最短路徑的情況下的最大經過城鎮數，以及在保證最短路徑下的最大城鎮數下的最大殲敵數量。然後根據記錄下來的這些資料，從終點開始搜尋，即可求出答案。

代碼如下

#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#define INF 0x3f3f3f3f
#define maxn 205
using namespace std;
stack<int> sta;
int cnt = 0;
int n, k;
string s, e;   //起點，終點 
int g[maxn][maxn];  //圖 
int v[maxn];   //i的敵人數量 
int dis[maxn];  //到i的最小距離 
int dv[maxn], dn[maxn]; //到i的最大殲敵數，到i的最大解放城鎮數 
void dfs1(int x) //求唯一路徑 
{
	sta.push(x);
	if(x == 1)
		return;
	for(int i = 1; i <= n; i ++){
		if(g[x][i] != INF && dis[x] - dis[i] == g[x][i] && dv[x] - dv[i] == v[x] && dn[x] - dn[i] == 1){
			dfs1(i);
			break;
		}
	}
}
void dfs2(int x) //求最短路數量 
{
	if(x == 1){
		cnt ++;
		return;
	}
	for(int i = 1; i <= n; i ++){
		if(i != x && g[x][i] != INF && dis[x] - dis[i] == g[x][i]){
			dfs2(i);
		}
	}
}
int main()
{
	
	cin >> n >> k >> s >> e;
	map<string, int> m;
	memset(dv, 0, sizeof(dv));
	memset(dn, 0, sizeof(dn));
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= n; j ++)
			g[i][j] = INF;
		g[i][i] = 0;
	}
	m[s] = 1; //起點為1 
	int t;  //終點 
	string str[maxn];
	str[1] = s;
	for(int i = 2; i <= n; i ++){
		string strr;
		int w;
		cin >> strr >> w;
		v[i] = w;
		m[strr] = i;
		str[i] = strr;
		if(strr == e)
			t = i;
	}
	for(int i = 0; i < k; i ++){
		string x, y;
		int d;
		cin >> x >> y >> d;
		g[m[x]][m[y]] = d;
		g[m[y]][m[x]] = d;
	}
	for(int i = 1; i <= n; i ++){
		dis[i] = g[1][i];
		if(i != 1 && g[1][i] != INF){
			dv[i] = v[i];
			dn[i] = 1;
		}
	}	
	bool vis[maxn] = {0};
	vis[1] = true;
	for(int i = 1; i < n; i ++){
		int minn = INF;
		int k;
		for(int j = 1; j <= n; j ++){
			if(!vis[j] && minn > dis[j]){
				minn = dis[j];
				k = j;
			}
		}
		vis[k] = true;
		for(int j = 1; j <= n; j ++){
			if(!vis[j] && g[k][j] != INF){
				if(dis[k] + g[k][j] < dis[j]){
					dis[j] = dis[k] + g[k][j];
					dv[j] = dv[k] + v[j];
					dn[j] = dn[k] + 1;
				}
				else if(dis[k] + g[k][j] == dis[j]){
					if(dn[j] < dn[k] + 1){
						dv[j] = dv[k] + v[j];
						dn[j] = dn[k] + 1;
					}
					else if(dn[j] == dn[k] + 1){
						dv[j] = max(dv[j], dv[k] + v[j]);
					}
				}
				
			}		
		}
	}
	dfs1(t);
	bool first = true;
	while(!sta.empty()){
		int top = sta.top();
		sta.pop();
		if(first)
			first = false;
		else
			cout << "->";
		cout << str[top];
	}
	cout << endl;
	dfs2(t);
	cout << cnt << " " << dis[t] << " " << dv[t] << endl;
	return 0;
}