# GOODA SPOJ Problem, Need Help!

Hello all!

I’ve been solving this question on Spoj GOODA - Good Travels. The problem statement is given a directed graph on N vertices and M edges with every vertex has a non-negative fun value F associated with it. You are given start vertex S and an end vertex E. You have to go from the S vertex to E vertex collecting fun value of intermediate vertices. Once you collect the fun value of a vertex then it fun value becomes zero, i.e you can’t collect the fun value from the single vertex more than once but you can visit any vertex any number of times. Constraints are given as
2 <= N <= 1e6,
1 <= M <= 1e6,
1 <= S,E <= N,
0 <= F <= 1e6, and
S != E

Now coming to my solution.
I first build the condensation graph of SCC’s of the above graph and stored the sum of fun values of each SCC component. Now the condensed graph will be acyclic. Now i just have to go from the SCC of vertex S to SCC of vertex E following the path that gives the maximum fun. I did it using dynamic programming but my solution kept on giving wrong answer on test #6 on Spoj.

Link to my solution is MY SOLUTION. Thank You very much for your time.

First I condesed the graph, later used DP to find the minimum distance from source to destination
//@Author- sitanshu

``````#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pii pair<int, int>

#define ff first

#define ss second

#define pb push_back

#define mii map<int, int>

#define umii unordered_map<int, ll>

#define vi vector<int>

#define vl vector<ll>

#define clr(val) memset(val, 0, sizeof(val))

const ll MAX = 1000009, MOD = 1e9 + 7;

#define OJ                            \

freopen("input.txt", "r", stdin); \

freopen("output.txt", "w", stdout);

vector<ll> visit;

int sc, des;

vi coin;

stack<int> st;

umii mp;

vector<vector<int>> ng;

void dfs1(int s)

{

visit[s] = 1;

{

if (visit[it] == 0)

dfs1(it);

}

st.push(s);

}

int counter;

void dfs2(int s)

{

visit[s] = counter;

mp[counter] += coin[s];

for (auto it : rdj[s])

{

if (visit[it] == -1)

dfs2(it);

}

}

ll topo(int s)

{

if (s == des)

return mp[des];

visit[s] = -1;

ll mx = -1;

for (auto it : ng[s])

{

if (visit[it] == -2)

topo(it);

mx = max(mx, visit[it]);

}

if (mx != -1)

visit[s] = mp[s] + mx;

return visit[s];

//visit[s] = 2;

}

int main()

{

//OJ;

int n, m;

cin >> n >> m >> sc >> des;

coin = vi(n + 1);

for (int i = 1; i <= n; i++)

cin >> coin[i];

adj = vector<vi>(n + 1), rdj = vector<vi>(n + 1);

int x, y;

for (int i = 0; i < m; i++)

{

cin >> x >> y;

rdj[y].pb(x);

}

visit = vector<ll>(n + 1, 0);

for (int i = 1; i <= n; i++)

{

if (visit[i] == 0)

dfs1(i);

}

fill(visit.begin(), visit.end(), -1);

counter = -1;

while (!st.empty())

{

int x = st.top();

st.pop();

if (visit[x] == -1)

{

++counter;

dfs2(x);

}

}

ng = vector<vi>(counter + 1);

sc = visit[sc];

des = visit[des];

for (int i = 1; i <= n; i++)

{

{

if (visit[i] != visit[it])

{

ng[visit[i]].push_back(visit[it]);

}

}

}

fill(visit.begin(), visit.end(), -2);

visit[des] = mp[des];

for (int i = 0; i <= counter; i++)

{

if (visit[i] == -2)

topo(i);

}

// cout << counter << " " << sc << " " << des << endl;

// for (int i = 0; i <= counter; i++)

// {

//     cout << i << ".) ";

//     for (auto it : ng[i])

//         cout << it << " ";

//     cout << endl;

// }

// for (int i = 0; i <= counter; i++)

//     cout << visit[i] << " " << mp[i] << endl;

// cout << endl;

cout << visit[sc] << endl;

return 0;

}``````