Question

1. (10 pts) Ginerva Weasley is playing with the network given below. Help her calculate the number of paths from node 1 to node 14. Hint: assume a "path" must have at least one edge in it to be well defined, and use dynamic programming to fill in a table that counts number of paths from each node j to 14, starting from 14 down to 1. 12>3456 7891011 121314

Answer 1

ANSWER:-

Run Debug Stop Share H Save Beautify Language C main.c 1 #include <bits/stdc++.h> 3 using namespace std 5 vector<int>adjlist[ 20]; 6 7 int visited[25]; 8 9 int dp[25]; 10 11 void bfs (int i) 12 13 14 <int > 15 queue 16 q; 17 q.push(i); 18 19 visited[i]-1; 20 21 while(!q.empty()) 23 25 int k q.front ); 26 27 q.pop); 28 29 for(int j-e;j<adjlist[k].size);j++)

31 32 33 dp[adjlist[k][j]] +dp[k]; 34 35 if(visited[ adjlist[k][j]]-1) 36 38 39 q.push(adjlist[k][j]); 40 41 visited[adjlist[k][j]]-1; 42 43 45 46 47 48 49 50 51 int main() 52 53 54 55 int u,v; 56 57 for(int i-0:i<24:1++ 58 59

60 62 63 adjlist[u].push_back (v); 64 65 for (int 1-0; 1(15;i++) 67 68 70 71 visited[i]- 72 73 dp[i] ; 74 75 76 77 dp[1] 1; 78 79 bfs(1): 80 81 for(int i-1;i<-14;i++) 82 83 cout<<"No of ways to "<<i<<" "<<dpfi] endl ; 84 85

OUTPUT SCREEN SHOT:-

9-- shortest.p 3 8 2 8 4 9 8 9 5 10 9 10 4 10 5 6 6 11 10 11 5 11 9 12 12 13 10 13 11 13 11 14 13 14 No of ways to 1 No of ways to 2 No of ways to 3 No of ways to 4 No of ways to 5 1 No of ways to 6 1 of ways to 7 2 of ways to 8 4 of ways to 9 S o of ways to 10 7 o of ways to 11 S o of ways to 12 5 o of ways to 13 21 o of ways to 14 30 No No No gureguru-He-15-Notebook-PC:/HomeworkLibs

COPY CODE:-

#include <bits/stdc++.h>

using namespace std;

vector<int>adjlist[20];

int visited[25];

int dp[25];

void bfs(int i)

{

queue <int> q;

q.push(i);

visited[i]=1;

while(!q.empty())

{

int k=q.front();

q.pop();

for(int j=0;j<adjlist[k].size();j++)

{

dp[adjlist[k][j]] += dp[k];

if(visited[adjlist[k][j]]!=1)

{

q.push(adjlist[k][j]);

visited[adjlist[k][j]]=1;

}

}

}

}

int main()

{

int u,v;

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

{

cin>>u>>v;

adjlist[u].push_back(v);

}

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

{

visited[i] = 0;

dp[i] = 0;

}

dp[1] = 1;

bfs(1);

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

cout<<"No of ways to "<<i<<" "<<dp[i]<<endl;

}