GO Classes DPP | Algorithm|QUALITY SCORE

Answer 1

Quality-score = maximum sum of edge-weights on any path from s to that vertex.

Compute path sums:
  score(s) = 0

  score(a) = s->a = 3

  score(b) = s->b = 1

  score(c) = max( s->a->c = 3+2 = 5,  s->b->c = 1+5 = 6 ) = 6

  score(d) = max( s->a->d = 3+6 = 9,
                  s->a->c->d = 3+2+1 = 6,
                  s->b->c->d = 1+5+1 = 7 ) = 9

Sum of quality-scores = 0 + 3 + 1 + 6 + 9 = 19

Answer 2

Answer: 19

quality score of vertices are:

s=0;

a=3;

b=1;
c=1+5;

d=3+6;
sum of all quality scores=0+3+1+6+9

 sum of all quality scores=19

Answer 3

Quality score of s= 0(given)

Quality score of  a= 3 (from weight edges)

Quality score of b= 1

Quality score of c= max(3+2, 1+5)=6

Quality score of d= max(3+6, 1+7)=9

so sum of all quality scores= 0+3+1+6+9=19 (ans)