Informatika gyűjtemény

NézetNyomtat

kb_szolga.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
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 )
        {
            // azért -1, mert az utolsó az csak a sorvégi 0-ás.
            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()
        {
            // a szerverektől bejárjuk az egészet, és mindenhova beírjuk a minimális távolságot
            // illetve megjegyezzük az apucit.
            
            int server;
            for( int i=0; i<serverIds.Length; i++ )
            {
                server = serverIds[i];
                DijkstraFromServer( server );
            }
            
            // output...
            
            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;
                
                // lekérjük a szomszédjait.
                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();
        }
    }
}
(Vissza)