Antonio081014's Algorithms Codes
The world is under the RULE.
Pages
Main
Google Code Jam
ACM - ICPC UVA
ACM-ICPC POJ
ACM-ICPC Spoj
USACO
Topcoder
算法艺术与信息学竞赛
Interview Problems
Mobile Devlopment
Friday, June 10, 2011
TCCC2003 Semifinals #4
Email This
BlogThis!
Share to Twitter
Share to Facebook
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!
No comments :
Post a Comment
Newer Post
Older Post
Home
Subscribe to:
Post Comments ( Atom )
No comments :
Post a Comment