using System;
internal class Program
{
const int INFINITY = int.MaxValue;
static int noOfNodes;
static int[,] graph;
static int mainNode;
static decimal influenceFactor;
static decimal[] nodeValues;
static int[] hopCounts;
static decimal[] influenceValues;
static int[] FindHopCounts(int[,] graph, int mainNode)
{
int[] hopCounts = new int[noOfNodes + 1];
bool[] sptSet = new bool[noOfNodes + 1];
for (int i = 1; i <= noOfNodes; i++)
{
hopCounts[i] = INFINITY;
sptSet[i] = false;
}
hopCounts[mainNode] = 0;
for (int count = 1; count <= noOfNodes; count++)
{
int u = MinHopCountNode(hopCounts, sptSet);
sptSet[u] = true;
for (int v = 1; v <= noOfNodes; v++)
{
if (!sptSet[v] && graph[v, u] != 0 &&
hopCounts[u] != INFINITY && hopCounts[u] + graph[v, u] < hopCounts[v])
{
hopCounts[v] = hopCounts[u] + graph[v, u];
}
}
}
for (int i = 1; i <= noOfNodes; i++)
{
if (i != mainNode && hopCounts[i] != INFINITY)
hopCounts[i]--;
}
return hopCounts;
}
static int MinHopCountNode(int[] hopCounts,
bool[] sptSet)
{
int minValue = INFINITY, minIndex = -1;
for (int v = 1; v <= noOfNodes; v++)
if (sptSet[v] == false && hopCounts[v] <= minValue)
{
minValue = hopCounts[v];
minIndex = v;
}
return minIndex;
}
static void CalculateInfluenceValues()
{
influenceValues = new decimal[noOfNodes + 1];
for (int i = 1; i <= noOfNodes; i++)
{
if (i != mainNode)
{
if (hopCounts[i] != INFINITY)
{
if (hopCounts[i] != 0)
influenceValues[i] = nodeValues[i] * influenceFactor * (1m / hopCounts[i]);
else
influenceValues[i] = decimal.MaxValue;
}
}
}
}
static void ReadInput()
{
Console.Write("Input number of nodes: ");
noOfNodes = int.Parse(Console.ReadLine());
Console.Write("Input main node: ");
mainNode = int.Parse(Console.ReadLine());
Console.Write("Input value for each node: ");
string[] strNodeValues = Console.ReadLine().Split(' ');
nodeValues = new decimal[noOfNodes + 1];
for (int i = 1; i <= noOfNodes; i++)
nodeValues[i] = int.Parse(strNodeValues[i - 1]);
Console.Write("Input influence factor: ");
influenceFactor = decimal.Parse(Console.ReadLine());
Console.WriteLine("Input the graph of connected nodes:");
graph = new int[noOfNodes + 1, noOfNodes + 1];
for (int i = 1; i <= noOfNodes; i++)
{
string[] s = Console.ReadLine().Split(',');
for (int j = 1; j <= noOfNodes; j++)
{
graph[i, j] = int.Parse(s[j - 1]);
}
}
}
static void PrintResults(int[] hopCounts, int mainNode)
{
Console.WriteLine();
for (int i = 1; i <= noOfNodes; i++)
{
if (i != mainNode)
{
string strHopCount = "";
if (hopCounts[i] == INFINITY)
strHopCount = "No path";
else
strHopCount = hopCounts[i].ToString();
string strInfluenceValue = "";
if (hopCounts[i] == INFINITY)
strInfluenceValue = "No path";
else if (influenceValues[i] == decimal.MaxValue)
strInfluenceValue = "Infinity";
else
strInfluenceValue = influenceValues[i].ToString();
Console.WriteLine("Hop Count from {0} to {1}: {2}\t\tInfluence value from {3} to {4}: {5}",
i, mainNode, strHopCount, i, mainNode, strInfluenceValue);
}
}
}
static void Main(string[] args)
{
ReadInput();
hopCounts = FindHopCounts(graph, mainNode);
CalculateInfluenceValues();
PrintResults(hopCounts, mainNode);
Console.ReadLine();
}
}
