2011-06-10 21:25:14Morris
d908. 4. 最佳路徑
http://zerojudge.tw/ShowProblem?problemid=d908
內容 ：
我們常以有向圖(Directed Graph)來表示物件與物件之間的關係。通常，有向圖是由多個的節點(Node)與多條的有向邊(Directed Edge)所連結而成。以圖八為例，A、B、C、D、E、F皆是節點，而節點與節點間是透過有向邊相連，包括了A->B、A->C、B->D、B->E、C->F及D->F。
我們並定義了由某一個節點出發拜訪其它節點途中所經過的邊合起來稱為一條路徑(Path)，例如A->B->E就是一條路徑(A稱為此路徑的起始節點，E稱為此路徑的終止節點)。同時，我們給予每一條邊一個權重(大於0、小於100的正整數)。這樣一來，我們就可以計算有向圖中每一條路徑的權重總和了。例如，A->B->E這條路徑的權重總和值是12，而A->B->D->F這條路徑的權重總和值是14，A->C這條路徑的權重總和值是1。
聰明的你，可否依據題目所給定的有向圖，在以有向圖中的某一個節點做為起始節點的所有可能路徑中，計算其中擁有最大權重總和的路徑之權重總和值為多少？我們假設在此討論的有向圖都不會存在有一條路徑的起始節點與終止節點是同一個。在上面的有向圖中，所有以A為起點的路徑之中，以A->B->D->F這條路徑的權重總和值最大(等於14)。
輸入說明
：
第一行為一個英文大寫字母 (A-Z)，表示要以哪個節點為起始節點來找擁有最大權重總和的路徑。
第二行為一個正整數n (1≤ n ≤ 100)，代表圖中有向邊的個數。
第三行起總共有n行，每一行有三個輸入，分別為某有向邊的起始節點(以大寫英文字母表示)、終止節點(以大寫英文字母表示)、以及權重(大於0、小於100的正整數)，皆以空白字元隔開。
輸出說明
：
請輸出一個正整數，為擁有最大權重總和的路徑之權重總和值。
範例輸入 ：
輸入範例一 B 6 A B 7 A C 1 B D 3 B E 5 C F 2 D F 4 輸入範例二 A 7 A B 4 A C 2 A D 3 B E 7 B G 1 B H 6 C E 5
範例輸出 ：
輸出範例一 7 輸出範例二 11
提示
：
出處
：
/**********************************************************************************/
/* Problem: d908 "4. 最佳路徑" from 2010三重考區 */
/* Language: C */
/* Result: AC (1ms, 267KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-09 23:39:34 */
/**********************************************************************************/
#include<stdio.h>
char s[2], x[2], y[2];
int n, a, Map[26][26] = {}, d, max;
int Used[26] = {};
void DFS(int now, int sum) {
int a;
if(sum > max) max = sum;
for(a = 0; a < 26; a++) {
if(Map[now][a] != 0 && Used[a] == 0)
Used[a] = 1, DFS(a, sum + Map[now][a]), Used[a] = 0;
}
}
main() {
scanf("%s", s); {
scanf("%d", &n);
for(a = 0; a < n; a++) {
scanf("%s %s %d", x, y, &d);
Map[x[0]-'A'][y[0]-'A'] = Map[x[0]-'A'][y[0]-'A'] > d ? Map[x[0]-'A'][y[0]-'A'] : d;
}
max = 0;
DFS(s[0] - 'A' , 0);
printf("%d\n", max);
}
return 0;
}