Restauracje
Kod był wyświetlany 1342 razy.
    /*
  Name: Restauracje
  Copyright: GPL GNU
  Date: 01-04-10 22:18
  Description: 
Bajdonald postanowił uruchomić w Bajtocji sieć restauracji. Jego pragnieniem jest, żeby każdy mieszkaniec mógł choćby raz w tygodniu wybrać się do jednej z nich. Wstępnie zaplanował już, w których miastach postawi swoje restauracje. Obawia się jednak, czy z każdego miasta będzie można w rozsądnym czasie dojechać do jakiejkolwiek z nich. Chciałby więc dowiedzieć się, jaką największą odległość trzeba pokonać, żeby dostać się do najbliższej restauracji. Jeśli ta odległość 
okaże się zbyt duża, będzie musiał zmienić swoje plany. Miasta w Bajtocji są połączone siecią dwukierunkowych autostrad. Wiadomo, że z każdego miasta można dojechać do każdego innego, choć nie zawsze bezpośrednio. Mieszkańcy Bajtocji żyją tylko w miastach.
Zadanie
Napisz program, który:
• wczyta ze standardowego wejścia mapę kraju oraz planowane miejsca budowy 
restauracji,
• wyznaczy maksymalną odległość jaką należy pokonać z pewnego miasta 
do najbliższej restauracji (to znaczy, spośród wszystkich odległości pomiędzy 
miastami a najbliższymi restauracjami, należy znaleźć tę największą),
• wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , i , , , oddzielone pojedynczymi odstępami, określające odpowiednio - liczbę miast w Bajtocji, liczbę planowanych restauracji oraz liczbę autostrad. Miasta są ponumerowane od do .
W każdym z kolejnych wierszy znajduje się jedna liczba - numer miasta, w którym ma być zbudowana restauracja. W każdym z następnych wierszy znajdują się trzy liczby całkowite , i , oddzielone pojedynczymi odstępami. Liczby te opisują jedną autostradę - autostrada łączy miasta i ( ), a jej długość wynosi km, .
Wyjście
W jedynym wierszu standardowego wyjścia powinna zostać zapisana jedna liczba całkowita, równa maksymalnej odlegości (w kilometrach) pomiędzy pewnym miastem, a najbliżej położoną restauracją.
Przykład
Dla danych wejściowych:
3 1 3
1
1 2 10
1 3 15
3 2 20
poprawną odpowiedzią jest:
15
*/
#include <iostream>
#include <conio.h>
#include <queue>
using namespace std;
struct Krawedz
{
        long nr,wartosc;
        Krawedz* next;
};
struct Lista
{
        Krawedz *glowa, *ogon;
};
Lista *ls;
long *glowna;
class Porzadkuj		
{
public:
	bool operator()(const int& a, const int &b)
	{
		if(glowna[a]>glowna[b])
			return true;
		return false;
	}
};
void Dodaj(long a, long b, long c)
{
        Krawedz *wsk=new Krawedz;
        wsk->next=NULL;
        wsk->nr=b;
        wsk->wartosc=c;
        if(ls[a].glowa==NULL)
                ls[a].glowa=ls[a].ogon=wsk;
        else
                ls[a].ogon=ls[a].ogon->next=wsk;
} 
int main()
{
	long n,k,m;
	cin>>n>>k>>m;
	glowna=new long[n+1];
	ls=new Lista[n+1];
	long *restauracje=new long[k];
	long MAX=1000000;
	for(long i=1;i<n+1;i++)
	{
		glowna[i]=MAX;
		ls[i].glowa=ls[i].ogon=NULL;
	}
	for(long i=0;i<k;i++)
	{
		long a;
		cin>>a;
		restauracje[i]=a;
		glowna[a]=0;
	}
	for(long i=0;i<m;i++)
	{
		long a,b,c;
		cin>>a>>b>>c;
		Dodaj(a,b,c);
		Dodaj(b,a,c);
	}
	priority_queue<long,vector<long>,Porzadkuj> kolejka;
	for(long i=0;i<k;i++)
	{
		kolejka.push(restauracje[i]);
		while(!kolejka.empty())
		{
			long nr=kolejka.top();
			Krawedz *wsk=ls[nr].glowa;
			kolejka.pop();
			while(wsk!=NULL)
			{
				if(glowna[wsk->nr]>wsk->wartosc+glowna[nr])
				{
					glowna[wsk->nr]=wsk->wartosc+glowna[nr];
					kolejka.push(wsk->nr);
				}
				wsk=wsk->next;
			}
		}
	}
	long maks=0;
	for(long i=1;i<n+1;i++)
	{
			if(glowna[i]>maks)
				maks=glowna[i];
	}
	cout<<maks;
	getch();
	return 0;
}
    
Pobierz plik tekstowy
Załączniki
Administrator WJL
PHP&SQL coded by NOVA-IT