【PAT甲級】1087 All Roads Lead to Rome (30分)

解題過程的小記錄，如有錯誤歡迎指出。

難度：四星（Dijkstra+DFS,本題的難點在于對字元串和下标之間的轉換，！！可以采用map的映射，建議使用map+鄰接矩陣再做一遍！！）

小導航~

• 題目分析
• • • 注意點
• 我的解題過程
• • • 思路
    • bug
    • 代碼
• dalao的代碼
• • • 借鑒點

題目分析

條條大路通羅馬，找出從給定起點到羅馬的路線，要求這條路線沿途花費最低，當花費相同時選擇到每個城市獲得的開心值的和最多的路線，當開心值的和相同選擇平均開心值最大的路線

注意點

1. 算平均開心值時，起始城市不算做分母

我的解題過程

思路

正常的Dijkstra+DFS套路題，不過本題資料量範圍過大（将三個大寫字母轉化為下标映射的範圍為262626），是以與之前的題目不同的是采用了鄰接表的方法，具體見代碼

bug

1. 在DFS中算開心值總和時，weight的下标寫錯，導緻無法将沿途開心值正确加入

代碼

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

const int INF = 1000000000;
const int MAXV = 26 * 26 * 26 + 5;
int n, k, st, ed;
string start;
vector<int> G[MAXV], C[MAXV], pre[MAXV], tempPath, Path;
int weight[MAXV];
bool vis[MAXV] = { false };
int cost[MAXV];//到達每一點最少花費
int cnt = 0;
int MaxHapp = 0, MaxAverHapp = 0;


int stringtoint(string s) {
	int result = 0;
	for (int i = 0; i < 3; i++) {
		result = result * 26 + (s[i] - 'A');
	}
	return result;
}

string inttostring(int index) {
	string result = "";
	for (int i = 0; i < 3; i++) {
		int d = index % 26;
		result += 'A' + d;
		index /= 26;
	}
	reverse(result.begin(), result.end());
	return result;
}

void Dijkstra(int s) {
	fill(cost, cost + MAXV, INF);
	cost[s] = 0;
	for (int i = 0; i < n; i++) {
		int u = -1, MIN = INF;
		for (int j = 0; j < MAXV; j++) {
			if (vis[j] == false && cost[j] < MIN) {
				u = j;
				MIN = cost[j];
			}
		}
		if (u == -1) return;
		vis[u] = true;
		for (int j = 0; j < G[u].size(); j++) {
			int v = G[u][j];
			if (vis[v] == false) {
				if (cost[v] > cost[u] + C[u][j]) {
					cost[v] = cost[u] + C[u][j];
					pre[v].clear();
					pre[v].push_back(u);
				}
				else if (cost[v] == cost[u] + C[u][j]) {
					pre[v].push_back(u);
				}
			}
		}
	}
}

void DFS(int v) {
	if (v == st) {
		cnt++;
		int temphapp = 0, tempaverahpp = 0;
		for (int i = 0; i < tempPath.size(); i++) {
			int id = tempPath[i];
			temphapp += weight[id];//***原來這裡寫成i了是以導緻weight無法加上去
		}
		tempaverahpp = temphapp / tempPath.size();
		tempPath.push_back(v);
		if (temphapp > MaxHapp) {
			Path = tempPath;
			MaxHapp = temphapp;
			MaxAverHapp = tempaverahpp;
		}
		if (temphapp == MaxHapp&&tempaverahpp > MaxAverHapp) {
			Path = tempPath;
			MaxAverHapp = tempaverahpp;
		}
		tempPath.pop_back();
	}
	tempPath.push_back(v);
	for (int i = 0; i < pre[v].size(); i++) {
		int id = pre[v][i];
		DFS(id);
	}
	tempPath.pop_back();
}

int main()
{
	scanf("%d%d", &n, &k);
	cin >> start;
	st = stringtoint(start);
	ed = stringtoint("ROM");
	for (int i = 0; i < n - 1; i++) {
		string city;
		int c, w;
		cin >> city;
		scanf("%d", &w);
		c = stringtoint(city);
		weight[c] = w;
	}
	for (int i = 0; i < k; i++) {
		string c1, c2;
		int dis, u, v;
		cin >> c1 >> c2;
		scanf("%d", &dis);
		u = stringtoint(c1);
		v = stringtoint(c2);
		G[u].push_back(v);
		G[v].push_back(u);
		C[u].push_back(dis);
		C[v].push_back(dis);
	}
	Dijkstra(st);
	DFS(ed);
	printf("%d %d %d %d\n", cnt, cost[ed], MaxHapp, MaxAverHapp);
	for (int i = Path.size() - 1; i >= 0; i--) {
		cout << inttostring(Path[i]);
		if (i != 0) printf("->");
	}
    return 0;
}
           

dalao的代碼

全部代碼因版權原因不放出來，大家可以自行去柳神部落格購買或者參考晴神的上機筆記~

借鑒點

1. 可以采用兩個map（一個是string到int的映射，另一個相反）來儲存城市名到下标之間的轉換（！！！太機智了~）