首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

題目很簡單，對於新手來說只需要會以下兩點:
1.存取圖、懂得圖的特性並提取圖的資料
2.用DFS(深度優先搜索)來解題(並非唯一解)

解題想法

使用map存取來達到Adjacency list的效果
一個用來存取點與點間的連接關係(ex: A點與B、C、E點有連結 所以mp[A]的字串有BCE)
一個用來存取點與點間的邊權重(用來計算maxd的)
再用DFS透過遍歷mp[起始點]的連接點”字串”(mp[x][0]、mp[x][1]…)
求maxd(最大路徑權重總和)

AC code

#include<bits/stdc++.h>
using namespace std;
map<char,string>mp;
map<char,vector<int> >mp2;
int maxd=0;
void dfs(char p,int sum){
	if(sum>maxd){
		maxd=sum;
	}
	for(int x=0;x<mp[p].size();x++){
		dfs(mp[p][x],sum+mp2[p][x]);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	char c,c1,c2;
	cin >> c;
	int n,num;
	cin >> n;
	while(n--){
		cin >> c1 >> c2 >> num;
		mp[c1]+=c2;
		mp2[c1].push_back(num);
	}
	dfs(c,0);
	cout << maxd << endl;
	return 0;
}

題目連結 : 99年北基區資訊學科能力競賽 4.最佳路徑