Description

As information travels farther away from its source, spreaders tend to select facts and offer their own interpretations. In other words, information becomes biased as it’s retold from person to person. This phenomenon is called Information Distortion.

A sensational story has been brought to the village by a person, who is regarded as the origin of the story. The story is then gossiped about from person to person. People spread the story to whoever they know. Every time when the story is passed to the next person, the correctness will shrink according to the closeness of the two people. Therefore, for each story receiver, different propagation paths may lead to different final correctness of the story.

The social network in this village is represented as a graph, where the nodes stand for the people, and the edges stand for the closeness of two people. Given the connected graph, we want to know: for each person in the village, which path brings the most reliable story (aka, the story with the highest correctness).

 

Hint

You can use log to calculate the final correctness for each node.

• EX: If a story travels through0 -> 2 -> 1in the above illustration, the final correctness is 0.9 * 0.8

  You can calculate the final correctness with |log₂0.9| +  |log₂0.8|. Make sure to round the log value L with round(L*100.0)/100.0 before summing them up.

• Syntax

  • Include library to use "log" and "abs".

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

  • Get the log value,temp, and round it to the 2nd decimal places. Get the absolute value.

    abs ( round(log2(temp)*100) / 100.0 )

Input

• An integer N represents the number of nodes, 2 ≤ N ≤ 100

• An integer R is the index of the origin node, 0 ≤ R ≤ N-1

• An N*N adjacency matrix represents the graph

  • Non-zero values C represent the edge weights between two nodes (aka closeness between two people)
    • 0.1 ≤ C ≤ 0.9
  • Zero values represent no edge between two nodes

Output

• Print out the origin of the story
  • output:The origin is: %ORIGIN
  • %ORIGIN: the origin node's index
• Print out the propagation path with the highest final correctness for each node in the graph, except the origin node's path
  • output:Path(%ORIGIN,%RECEIVER): %ORIGIN -> ... -> ... -> %RECEIVER
  • %ORIGIN: the origin node's index
  • %RECEIVER: the receiver node's index
  • The nodes in the middle are also represented with the index
  • If there are multiple paths with the same final correctness, choose the path that first leads to the node with the smallest index.
    • ex: Path_1 and Path_2 have the same final correctness 
    • Node_1 and Node_2 are both the second node of the path. 1 < 2, so choose Path_1.

Sample Input  Download

Sample Output  Download

Tags

Discuss