【Zerojudge】d908

Problem here

Solution

DFS

#include <iostream>
#include <memory.h>
using namespace std;
int rat[30][30];
bool visit[30];
int sum;
void solve(int here, int cost){
    sum = max(sum, cost);
    visit[here] = true;
    for(int i = 0; i < 26; i++){
        if(visit[i] == false && rat[here][i] != 0){
            solve(i, cost+rat[here][i]);
            visit[i] = false;
        }
    }
}

int main(){
    char start;
    while(cin >> start){
        int n;cin >> n;
        sum = 0;
        memset(rat, 0, sizeof(rat));
        memset(visit, false, sizeof(visit));
        while(n--){
            char a, b;int w;
            cin >> a >> b >> w;
            rat[a-'A'][b-'A'] = max(rat[a-'A'][b-'A'], w);
        }
        solve(start-'A', sum);
        cout << sum << endl;

    }

    return 0;
}