Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 3 KB
using System;
using System.IO;
using System.Collections.Generic;
namespace Szolga
{
class Computer
{
public int distance = -1;
public int daddy = -1;
public bool alreadyChecked = false;
public int[] neighbours;
public void Output(StreamWriter outs)
{
if( distance == -1 ) distance = 0;
outs.WriteLine("{0} {1}", distance, daddy+1);
}
}
class Network
{
public int[] serverIds;
private Computer[] computers;
private int maxDistance = 0;
public Network( int computers, int servers )
{
serverIds = new int[servers];
this.computers = new Computer[computers];
for( int i=0; i<computers; i++ ) {
this.computers[i] = new Computer();
}
}
public void SetServers( string[] servers )
{
for(int i = 0; i < serverIds.Length; i++)
{
serverIds[i] = int.Parse(servers[i])-1;
}
}
public void ConnectWith( int id, string[] neighbours )
{
computers[id].neighbours = new int[neighbours.Length-1];
for( int i = 0; i < neighbours.Length-1; i++ )
{
computers[id].neighbours[i] = int.Parse(neighbours[i])-1;
}
}
public void DoMagic()
{
int server;
for( int i=0; i<serverIds.Length; i++ )
{
server = serverIds[i];
DijkstraFromServer( server );
}
StreamWriter outs = new StreamWriter("szolga.ki");
outs.WriteLine(maxDistance);
for( int i=0; i<computers.Length; i++ )
{
computers[i].Output(outs);
}
outs.Close();
}
public void DijkstraFromServer( int server )
{
Queue<int> q = new Queue<int>( computers.Length );
q.Enqueue(server);
computers[server].distance = 0;
computers[server].daddy = server;
for( int i=0; i<computers.Length; i++ )
{
computers[i].alreadyChecked = false;
}
int comp;
while( q.Count != 0 )
{
comp = q.Dequeue();
if( computers[comp].alreadyChecked ) continue;
computers[comp].alreadyChecked = true;
int other;
for( int i=0; i<computers[comp].neighbours.Length; i++ )
{
other = computers[comp].neighbours[i];
if( !computers[other].alreadyChecked ) {
if( computers[other].distance == -1 || computers[comp].distance+1 <= computers[other].distance )
{
q.Enqueue(other);
computers[other].distance = computers[comp].distance+1;
if( computers[other].distance > maxDistance )
maxDistance = computers[other].distance;
computers[other].daddy = comp;
}
}
}
}
}
}
class Program
{
private Network network;
public Program()
{
StreamReader ins = new StreamReader("szolga.be");
string[] line = ins.ReadLine().Split(' ');
int n = int.Parse(line[0]);
int k = int.Parse(line[1]);
network = new Network( n, k );
line = ins.ReadLine().Split(' ');
network.SetServers( line );
for(int i = 0; i < n; i++)
{
line = ins.ReadLine().Split(' ');
network.ConnectWith( i, line );
}
ins.Close();
network.DoMagic();
}
public static void Main(string[] args)
{
new Program();
}
}
}