txhai12's blog

By txhai12, history, 6 months ago, In English

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]){


// the normal and get ac

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

// i think problem just need to, but i get WA
// =====

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 :((

Read more »

  • Vote: I like it
  • +2
  • Vote: I do not like it