### txhai12's blog

By txhai12, history, 6 months ago,

Hi, I'm just done like 40 submission of this problem (https://www.spoj.com/problems/GOODA/). I really stuck thinking why my solution get ac, pls help me. Give a directed graph, an array of value of each city, s — start city, e — end city and ask for choosing a path from s to e and the path have maximum value of city on the path. Guarantee that e is reachable from s.

I converting the directed graph to condensation graph (DAG) (by this technique https://cp-algorithms.com/graph/strongly-connected-components.html) and do dp. But i think in the first dfs(dfs1) I just need to dfs1 start from the s, in stead of staring from every node u that used[u] = false, bcuz e is reachable from s.

void dfs1(int u){
used[u] = true;
if(!used[v]){
dfs1(v)
}
}

st.epb(u);
}

// the normal and get ac

for(int i = 1 ; i <= n ; i++){
if (!used[i]){
dfs1(i);
}
}
// ====

// i think problem just need to, but i get WA
dfs1(s);
// =====


Here is my code get ac, https://ideone.com/6KwRpb

Can u guys give me some test case that my think will wrong. Thanks for reading, sorry for my bad English :((