IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Задача с графом, на алгоритм Дейкстры
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 13
Пол: Мужской

Репутация: -  1  +


Олимпиада по алхимии
(Время: 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.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
c-ch   Задача с графом   5.04.2009 14:51


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 20:37
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name