alan23273850 的刷題筆記
d908: 4. 最佳路徑
Tags: graph
出處：https://zerojudge.tw/ShowProblem?problemid=d908
提交：https://zerojudge.tw/Submissions?problemid=d908&account=allllllan123456
問題：給定一張有至多 26 個點、有 $n\in[1,100]$ 條權重介於 $[1,99]$ 之邊的有向無環圖 (DAG)，現在從指定節點開始走訪，請問在所有可行的路徑之中，最大可能的權重和是多少？
解法：很簡單，就單純的 DFS 而已，而且因為這題的邊權重都是正的，只要走到盡頭的時候再更新最大權重和即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4int maX;
5vector<pair<int, int>> adj[26];
6
7void dfs(int v, int sum) {
8 for (const auto &pii: adj[v])
9 dfs(pii.first, sum + pii.second);
10 if (adj[v].empty())
11 maX = max(maX, sum);
12}
13
14int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
15 int c, n; char start, a, b;
16 cin >> start >> n;
17 while (n--)
18 cin >> a >> b >> c,
19 adj[a-'A'].push_back(pair<int, int>(b-'A', c));
20 maX = INT_MIN;
21 dfs(start-'A', 0);
22 cout << maX << '\n';
23 return 0;
24}