1 1
1 1
3
100 1 0
100 1 1
0 1 0

answer: 1 0

I wa many times.
Thank you very much!

if a route is defined by the stops: 1, 2, 4. Can they go from 4 to 2 then to 1 or is it one-way route?

test 11.please give me some test.thx!

Why that? Who can give me the test case that will fail like this?

any hints???

I don't know why I got wa on 17,is there any tests??Please help me, it drives me crazy for 4 hours/

I used Floyd and get WA 4.
I use BFS, but I get WA 4. :(

Why?
What is the special effect? What features at our tram routes?

4 3
3 1 2 4
2 2 3
2 3 4
3
27 1 0
15 4 0
45 4 0

The path is a circle.

Here is my code:


type My=record
       den,ost,sez:longint;
     end;
     Matr=array[1..101,1..101] of longint;

var m,n,l,i,j,h,k,min,o,sum:longint;
    a: Matr;
    q: array[1..101] of longint;
    w: array[1..101] of my;
    f:boolean;

procedure floyd(var  c:matr);
var i,j,k:longint;
begin
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if c[i,k]+c[k,j]<c[i,j] then c[i,j]:=c[i,k]+c[k,j];
  for i:=1 to n do c[i,i]:=0;
end;



begin
  readln(n,m);
  for i:=1 to n do
    for j:=1 to n do a[i,j]:= 1000000;
  for i:=1 to m do begin
    read(l);
    for j:=1 to l do read(q[j]);
    for j:=1 to l-1 do
      for h:=j+1 to l do begin
        a[q[j],q[h]]:=4;
        a[q[h],q[j]]:=4;
      end;
  end;
  floyd(a);
  readln(k);
  for i:=1 to k do readln(w[i].den,w[i].ost,w[i].sez);
  min:=1000000;
  for i:=1 to n do begin
  sum:=0;
    f:=true;
    for j:=1 to k do begin
      if w[j].sez=0 then
        if (w[j].den<a[i,w[j].ost]) then begin
          f:=false;
          break;
        end
        else sum:=sum+a[i,w[j].ost];
    end;

    if (f) and (min>sum) then begin
      o:=i;
      min:=sum;
    end;
  end;

  if min=1000000 then writeln(0)
  else writeln(o,' ',min);
end.

Should I use Dijkstra's algorithm several times for each friend or just floyd-warshall?

what is Month tram ticket?

It may be quite obvious from the problem statement, but it wasn't for me, so i guess i'll just write it here:
Whoever has a monthly tram ticket travels for free regardless of route switches. The others pay 4 rubles for every route they take.
Cost me a few submits, because i thought the monthly ticket applies for the initial route, but not for the subsequent switches ...

rt~~

What the hell? I use BFS, all tests given here my program answers correct, but WA1! What could it be?

why wa2???
program ural;
var n,m,i,k,j,r,p:byte;
    a:array[1..100]of byte;
    b:array[1..100,1..100]of byte;
    d:array[1..100]of integer;
    z,t:integer;
label 1;
begin
  readln(n,m);
  for i:=1 to m do
    begin
      read(k);
      for j:=1 to k do
        read(a[j]);
      for j:=1 to k do
        for r:=1 to k do
          if j<>r then
            begin
              b[a[j],a[r]]:=1;
              b[a[r],a[j]]:=1;
            end;
    end;
  readln(m);
  for i:=1 to m do
    begin
      readln(d[i],a[i],p);
      if p=1 then
        d[i]:=101
      else
        d[i]:=d[i] div 4;
    end;
  for i:=1 to n do
    for j:=1 to n-1 do
      if i<>j then
        for r:=j+1 to n do
          if r<>i then
            if(b[j,i]>0)and(b[i,r]>0)then
              begin
                t:=b[j,i]+b[i,r];
                if(b[j,r]=0)or(t<b[j,r])then
                  begin
                    b[j,r]:=t;
                    b[r,j]:=t;
                  end;
              end;
  z:=255;
  for i:=1 to n do
    begin
      t:=0;
      for j:=1 to m do
        if a[j]<>i then
          if(b[a[j],i]>0)and(b[a[j],i]<=d[j])then
            begin
              if d[i]<>101 then
                inc(t,b[a[j],i]);
            end
          else
            goto 1;
      if t<z then
        begin
          k:=i;
          z:=t;
        end;
1:  end;
  if z=255 then
    writeln(0)
  else
    writeln(k,' ',z*4);
end.