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

Общий форум

Problem 1085. Встреча
Послано RocBoy-D 7 апр 2012 00:17
wa #21. Can anybody help me?

Program P1;
Var
  Map: Array[1..100,1..100] of Integer;
  S,G,F: Array[1..100] of Integer;
  A,I,B,J,N,M,K,L,P,R: Integer;

Begin
  Readln(N,M);
  For A:=1 to N do
    For B:=1 to N do
      Map[A,B]:=16000;

  For I:=1 to M do begin
    Read(L);
    For J:=1 to L do
      Read(S[J]);
    For A:=1 to L do
      For B:=1 to L do
        Map[S[A],S[B]]:=1;
  End;

  For A:=1 to N do
    For B:=1 to N do
      For I:=1 to N do
        If Map[A,B]>Map[A,I]+Map[I,B] then Map[A,B]:=Map[A,I]+Map[I,B];

  Read(K);
  A:=0;
  For I:=1 to K do begin
    Readln(G[I],S[I],F[I]);
    A:=A+G[I];
  End;

  P:=0;
  R:=P;
  For I:=1 to N do begin
    P:=0;
    For J:=1 to K do begin
      If I=S[J] then begin P:=P+G[J]; continue; End;
      If Map[I,S[J]]=16000 then begin P:=0; Break; End;
      If (Map[I,S[J]]*4>=G[J]) and (F[J]=0) then begin P:=0; Break; End;
      If F[J]=1 then begin P:=P+G[J]; Continue; End;
      P:=P+G[J]-Map[I,S[J]]*4;
    End;
    If P>R then begin
      R:=P;
      L:=I;
    End;
  End;
  If R<>0 then Writeln(L,' ',A-R)
          else Writeln(0);
End.