ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1085. Встреча

Why WA on test #2?
Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 5 июл 2004 14:49
program ural1085;
const
  max=100;
  price=4;
  inf=65535;
var
  cost:array[1..max,1..max]of word;
  money:array[1..max]of word;
  stop:array[1..max]of byte;
  mt:array[1..max]of boolean;
  n,m,l,k,ans,i,j:byte;
  min,total:longint;
  ok:boolean;
begin
  {Make graph}
  fillchar(cost,sizeof(cost),255);
  readln(n,m);
  for i:=1 to m do begin
    read(l);
    for j:=1 to l do
      read(stop[j]);
    for j:=1 to l-1 do
      for k:=j+1 to l do begin
        cost[stop[j],stop[k]]:=price;
        cost[stop[k],stop[j]]:=price;
      end;
  end;
  for i:=1 to n do
    cost[i,i]:=0;

  {Floyd}
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if (cost[i,k]<inf) and (cost[k,j]<inf) then
          if cost[i,k]+cost[k,j]<cost[i,j] then
            cost[i,j]:=cost[i,k]+cost[k,j];

  {Friends info}
  readln(k);
  for i:=1 to k do begin
    readln(money[i],stop[i],j);
    mt[i]:=j=1;
  end;

  {Main}
  ans:=0;min:=maxlongint;
  for i:=1 to n do begin
    total:=0;ok:=true;
    for j:=1 to k do
      if (cost[stop[j],i]=inf) or not mt[j] and (cost[stop[j],i]>money[j]) then begin
        ok:=false;
        break;
      end
      else
        inc(total,cost[stop[j],i]);
    if ok then
      if total<min then begin
        ans:=i;
        min:=total;
      end;
  end;

  {Output}
  if ans=0 then
    writeln(0)
  else
    writeln(ans,' ',min);
end.
Re: Why WA on test #2?
Послано Slava Medvedev(PetrSU) 27 июл 2004 16:05
Maigo Akisame (maigoakisame@yahoo.com.cn) писал(a) 5 июля 2004 14:49
program ural1085;
const
  max=100;
  price=4;
  inf=65535;
var
  cost:array[1..max,1..max]of word;
  money:array[1..max]of word;
  stop:array[1..max]of byte;
  mt:array[1..max]of boolean;
  n,m,l,k,ans,i,j:byte;
  min,total:longint;
  ok:boolean;
begin
  {Make graph}
  fillchar(cost,sizeof(cost),255);
  readln(n,m);
  for i:=1 to m do begin
    read(l);
    for j:=1 to l do
      read(stop[j]);
    for j:=1 to l-1 do
      for k:=j+1 to l do begin
        cost[stop[j],stop[k]]:=price;
        cost[stop[k],stop[j]]:=price;
      end;
  end;
  for i:=1 to n do
    cost[i,i]:=0;

  {Floyd}
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if (cost[i,k]<inf) and (cost[k,j]<inf) then
          if cost[i,k]+cost[k,j]<cost[i,j] then
            cost[i,j]:=cost[i,k]+cost[k,j];

  {Friends info}
  readln(k);
  for i:=1 to k do begin
    readln(money[i],stop[i],j);
    mt[i]:=j=1;
  end;

  {Main}
  ans:=0;min:=maxlongint;
  for i:=1 to n do begin
    total:=0;ok:=true;
    for j:=1 to k do
      if (cost[stop[j],i]=inf) or not mt[j] and (cost[stop[j],i]>money[j]) then begin
        ok:=false;
        break;
      end
      else
        inc(total,cost[stop[j],i]);
    if ok then
      if total<min then begin
        ans:=i;
        min:=total;
      end;
  end;

  {Output}
  if ans=0 then
    writeln(0)
  else
    writeln(ans,' ',min);
end.


Sorry, See below

Edited by author 27.07.2004 16:09
Re: Why WA on test #2?
Послано Slava Medvedev(PetrSU) 27 июл 2004 16:07
A
Maigo Akisame (maigoakisame@yahoo.com.cn) писал(a) 5 июля 2004 14:49
program ural1085;
const
  max=100;
  price=4;
  inf=65535;
var
  cost:array[1..max,1..max]of word;
  money:array[1..max]of word;
  stop:array[1..max]of byte;
  mt:array[1..max]of boolean;
  n,m,l,k,ans,i,j:byte;
  min,total:longint;
  ok:boolean;
begin
  {Make graph}
  fillchar(cost,sizeof(cost),255);
  readln(n,m);
  for i:=1 to m do begin
    read(l);
    for j:=1 to l do
      read(stop[j]);
    for j:=1 to l-1 do
      for k:=j+1 to l do begin
        cost[stop[j],stop[k]]:=price;
        cost[stop[k],stop[j]]:=price;
      end;
  end;
  for i:=1 to n do
    cost[i,i]:=0;

  {Floyd}
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if (cost[i,k]<inf) and (cost[k,j]<inf) then
          if cost[i,k]+cost[k,j]<cost[i,j] then
            cost[i,j]:=cost[i,k]+cost[k,j];

  {Friends info}
  readln(k);
  for i:=1 to k do begin
    readln(money[i],stop[i],j);
    mt[i]:=j=1;
  end;

  {Main}
  ans:=0;min:=maxlongint;
  for i:=1 to n do begin
    total:=0;ok:=true;
    for j:=1 to k do
      if (cost[stop[j],i]=inf) or not mt[j] and (cost[stop[j],i]>money[j]) then begin
        ok:=false;
        break;
      end
      else
        if mt[j] then   {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
          inc(total,cost[stop[j],i]);
    if ok then
      if total<min then begin
        ans:=i;
        min:=total;
      end;
  end;

  {Output}
  if ans=0 then
    writeln(0)
  else
    writeln(ans,' ',min);
end.
What do u mean?
Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 27 июл 2004 17:17
Re: What do u mean?
Послано Saturn 28 июл 2004 13:28
It's mean you did't read the solution above carefully
Did you see this (!!!!!!!!!!!!!!!!) in the solution?
Thanx. But you omitted a 'not'.
Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 29 июл 2004 17:06