TCCC2003 Semifinals #4

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Source Code:

Division One - Level One:

Solution

Actually, this is a pretty easy problem, just like The Problem on POJ1088, however, I misunderstood the meaning of the longest path, I thought I needed to count the # of hops needed. Actually, the longest path is the biggest cost. Just DFS it.

Source Code:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class Circuits {
public:
    int grid[51][51];
    int cost[51];
    int N;
    int howLong(vector <string>, vector <string>);
    void dfs(int x){
        if(cost[x] >=0) return ;
        cost[x] = 0;
        for(int i=0; i<N; i++){
            if(grid[x][i] >= 0){
                dfs(i);
                cost[x] = max(cost[x], cost[i] + grid[x][i]);
            }
        }
    }
};

int Circuits::howLong(vector <string> con, vector <string> costs) {
    N = con.size();
    memset(grid, -1, sizeof(grid));
    memset(cost, -1, sizeof(cost));
    for(int i=0; i<N; i++){
        stringstream s1(con[i]), s2(costs[i]);
        int id, c;
        while(s1 >> id && s2 >> c){
            grid[i][id] = c;
        }
    }
    int ret = 0;
    for(int i=0; i<N; i++){
        if(cost[i] < 0){
            dfs(i);
                ret = max(ret, cost[i]);
        }
        cout << cost[i] << ", ";
    }
    cout << endl;
    return ret;
}

//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!