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;↵
for(auto v : adj[u]){↵
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 :((↵
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;↵
for(auto v : adj[u]){↵
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 :((↵
