[Мы решаем ваши проблемы с Си и Паскалем ]
Главная » Статьи » Задачи с acm.timus.ru » Пакет решений на 15.03.08
1085
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.
Категория: Пакет решений на 15.03.08 | Добавил: solver (15.03.2008)
Просмотров: 799