# ECAPR205 (Bob Wants Cookies) - Editorial

Author: Sunita Sen
Tester: Arnab Chanda
Editorialist: Sunita Sen

EASY - MEDIUM

# PREREQUISITES:

GRAPH-BFS/DFS,Dijkstra

# PROBLEM:

Given a graph and two nodes S and K find the number of shortest simple paths from S to K.

# EXPLANATION:

We will be using DFS to solve this problem.
Let us look at DFS code:

``````DFS(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS(G, w)

``````

But hey, visiting nodes is not enough we must add weight of path:

``````DFS-withweight(G, sum, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
sum = sum + weight[s][w] // weight[s][w] weight of path s->w
DFS(G, sum, w)

``````

However, this method will fail when two separate paths will converge at a node, and both will lead to a minimum value path.
Like this one:

Say we follow the path 1->3->4 then we will be marking node 3 as visited, then 2->3->4 will become invalid.
So we can do this:

``````DFS-withweight(G, sum, s):
for all neighbours w of s in Graph G:
if w is not visited:
mark s as visited
sum = sum + weight[s][w] // weight[s][w] weight of path s->w
DFS(G, sum, w)
sum = sum - weight[s][w]
mark s as not visited
``````

Lastly, we need to store the count of shortest simple paths. If the path sum from S to K is already equal to minimum sum, then we will increment our count value, and if path sum is less than minimum sum, then, we will set the minimum sum and count value will be equal to 1.

``````DFS-withweight(G, sum, s):
if s is equal to k:
if sum < minimum sum:
minimum sum = sum
count = 1
else if sum = minimum sum:
count = count + 1

return

for all neighbours w of s in Graph G:
if w is not visited:
mark s as visited
sum = sum + weight[s][w] // weight[s][w] weight of path s->w
DFS(G, sum, w)
sum = sum - weight[s][w]
mark s as not visited
``````

# Bonus: Solving using dijkstra

We can also solve this problem using dijkstraâ€™s algorithm.

Number of shortest simple path till K can be reached in two ways:
Let a parent of K is some node A.

1. If the path sum between S to K via A is less than the already calculated path sum of K: The number of shortest paths from S to K will be equal to number of shortest paths from S to A.
2. If the path sum between S to K via A is equal to the already calculated path sum of K: The number of shortest paths from S to K will be equal to number of shortest paths from S to K + number of shortest paths from S to A.

Here, we will keep calculating the number of shortest paths for each node as we calculate the minimum distance from source to a vertex in dijkstraâ€™s algorithm.
Refer to: Soham Chakrabartiâ€™s solution

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define pb   push_back
#define F    first
#define S    second
const ll INF = 1e9;
vector<pair<ll,ll>> v[1000];
bool visited[2000];
ll minsum = INF,amt=0;

void dfs(ll k,ll sum,ll target){
if(k == target){
if(sum<minsum){
minsum = sum;
amt = 1;
}
else if(sum==minsum){
amt++;
}
return;
}

for(auto i: v[k]){
if(!visited[i.F]){
visited[i.F] = true;
dfs(i.F,sum+i.S,target);
visited[i.F] = false;
}
}

}

int main() {
ll t=1;
cin>>t;
while(t--){
minsum = INF;
amt = 0;
ll n,m;
cin>>n>>m;
rep(i,m){
ll a,b,c;
cin>>a>>b>>c;
v[a].push_back(make_pair(b,c));
}
ll k,s;
cin>>s>>k;
dfs(s,0,k);
cout<<amt<<endl;
rep(i,n){
v[i].clear();
}
mem(visited,false);

}

}
``````
4 Likes

Thank you for the editorial! I was not able to did this problem during contest so I was eagerly waiting for the editorial . Dijkstraâ€™s solution is very nice and easy to implement.

2 Likes

I used the same logic but got WA. Can anyone help me with it?
My code: CodeChef: Practical coding for everyone