Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задача с графом

Автор: c-ch 5.04.2009 14:51

Олимпиада по алхимии
(Время: 1 сек. Память: 16 Мб Сложность: 53%)
В государстве алхимиков есть N населённых пунктов, пронумерованных числами от 1 до N, и M дорог. Населённые пункты бывают двух типов: деревни и города. Кроме того, в государстве есть одна столица (она может располагаться как в городе, так и в деревне). Каждая дорога соединяет два населённых пункта, и для проезда по ней требуется Ti минут. В столице было решено провести 1-ю государственную командную олимпиаду по алхимии. Для этого во все города из столицы были отправлены гонцы (по одному на город) с информацией про олимпиаду.

Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберётся до своего города. Считается, что гонец во время пути нигде не задерживается.

Входные данные

Во входном файле INPUT.TXT сначала записаны 3 числа N, M, K — количество населенных пунктов, количество дорог и количество городов (2<=N<=1000, 1<=M<=10000, 1<=K<=N). Далее записан номер столицы C (1<=C<=N). Следующие K чисел задают номера городов. Далее следуют M троек чисел Si, Ei, Ti, описывающих дороги: Si и Ei — номера населенных пунктов, которые соединяет данная дорога, а Ti — время для проезда по ней (1<=Ti<=100).

Гарантируется, что до каждого города из столицы можно добраться по дорогам (возможно, через другие населенные пункты).

Выходные данные

В выходной файл OUTPUT.TXT выведите K пар чисел: для каждого города должен быть выведен его номер и минимальное время, когда гонец может в нем оказаться (время измеряется в минутах с того момента, как гонцы выехали из столицы). Пары в выходном файле должны быть упорядочены по времени прибытия гонца, а в случае совпадения времени следует сортировать эти пары по номерам городов.

Примеры

5 4 5 1
1 2 3 4 5
1 2 1
2 3 10
3 4 100
4 5 100
ответ
1 0
2 1
3 11
4 111
5 211

5 5 3 1
2 4 5
2 1 1
2 3 10
3 4 100
4 5 100
1 5 1
ответ
2 1
5 1
4 101

мой вариант не проходит по времени раза в 3, хотя в качестве комментария было сказано, что сортировка пузырьком сгодится sad.gif
прошу помощи unsure.gif

program Project1;
uses math;
const maxcount=1000;
type town=record n,l:integer end;
townar=array[1..maxcount]of town;
graph=array[1..maxcount,1..maxcount]of integer;
var
a:graph;
n,m,k,e,i,j,x,y,z,last,min_dist:integer;
done:array[1..maxcount]of boolean;
dist:array[1..maxcount]of integer;
towns:townar;
f:text;
t:town;
r:real;

begin
for I := 1 to maxcount do
for j := 1 to maxcount do a[i,j]:=$ffff;

assign(f,'input.txt');
reset(f);
readln(f,n,m,k,e);
for I := 1 to k do read(f,towns[i].n);
for I := 1 to n do
begin
readln(f,x,y,z);
a[x,y]:=z;
a[y,x]:=z;
end;
close(f);

for i := 1 to n do
begin
dist[i]:=$ffff;
done[i]:=false;
end;

dist[e]:= 0;
done[e]:= true;
last:= e;
for i:= 1 to N-1 do
begin
for x:= 1 to N do
if (a[last,x]<>0)and(not done[x])
then dist[x]:= min(dist[x],dist[last]+ a[last,x]);
min_dist:= $ffff;
for x:= 1 to N do
if (not done[x])and(min_dist>dist[x])
then begin min_dist:= dist[x];
last:= x;
end;
done[last]:= true;
end;
for i := 1 to k do towns[i].l:=dist[towns[i].n];
for i := 1 to k do
for j := i to k do
begin
if towns[j].l<towns[i].l then
begin
t:=towns[i];
towns[i]:=towns[j];
towns[j]:=t
end;
if (towns[j].l=towns[i].l)and(towns[j].n<towns[i].n) then
begin
t:=towns[j];
towns[j]:=towns[i];
towns[i]:=t
end;
end;
assign(f,'output.txt');
rewrite(f);
for I := 1 to k do writeln(f,towns[i].n,' ',towns[i].l);
close(f);
end.