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! I know,I used "<money[i]" You should use "<=money[i]" oh thanks, man, it helped me) 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??? Ok I forgot about this: (if there are several numbers choose the minimal one) I don't know why I got wa on 17,is there any tests??Please help me, it drives me crazy for 4 hours/ Try this: 4 1 2 2 3 2 10 1 1 10 4 1 0 Edited by author 22.11.2006 03:43 Thank you a lot! Thank you. It helped me too! 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? YAHOO!!! I got AC. if you get WA4 -> travel card = unlimit if you get WA6 -> test when answer = 0 4 3 3 1 2 4 2 2 3 2 3 4 3 27 1 0 15 4 0 45 4 0 my solutin gives "4 4". But still WA#15 my solution also gives "4 4". But still WA#15, what can i do? 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. Try this test: 4 2 2 1 2 2 3 4 2 0 1 1 0 3 1 Thank you very much. Seems it's a common mistake :) thank you very much ! I have got AC. THX! Very foolish mistake... Should I use Dijkstra's algorithm several times for each friend or just floyd-warshall? ..? good q .. but .. ! all the edge's cost's are 1 .. so .. :-) use BFS .. for every friend from its starting position :-) its n*k :-) .. but i got WA 14 :-( ... ~~~~~~~~~~~~~~~~~~~~~~~~~~~ now i get it .. the WA's in the discuss are very useful :-) and .. with my o(n*k) i had .. 0.031 264 KB Edited by author 13.09.2010 22:03 Edited by author 13.09.2010 22:03 Are you sure it's O(n*k)? I used DFS from every tramstop to find how much it costs for all of friends to meet here. This test helped me a lot (it's funny to draw circles): 13 5 3 1 2 3 3 4 5 3 3 6 7 3 3 8 9 3 8 10 4 11 6 12 8 13 1 I corrected all mistakes by adding different situations on this tram-map :) what is Month tram ticket? This "month tram ticket" allows you to use tram as much times as you want without any payment. 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 ... What the hell? I use BFS, all tests given here my program answers correct, but WA1! What could it be? Oh, I finally had done it... The first idea wasn't good. Just another BFS AC'es. 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. I can only say, that answer to the test 2 is 4 12. Program like this: begin write('4 12'); end. gives WA#4. I don't know, what is your WA2, but my WA2 is people who spend his money, when they have month ticket. Try this: 4 3 2 1 2 2 2 3 2 3 4 3 27 1 1 15 4 0 45 4 0 Answer is 4 0. I hope, it helps. Sorry for my bad english. You are right Thnx a lot Edited by author 02.11.2010 23:03 |
|