My solution uses simple Floyd algo.It passed all tests on this board, but still gets WA.

Edited by author 02.04.2009 12:58

help Me please

Test 1.
Need three tickets -> 3 * 4 = 12
And need money (two tickets) for first pessenger for distance from 1 to 4.
All sum = 12 + 2 * 4 = 20.

Please, tell me, what I dont understand.

Sorry, I bad speak english.

i mean like this:

4 3
3 1 2 150 <----this stop is greater than 100
2 2 3
2 3 4
3
27 1 0
15 4 0
45 4 0

One of my solutions can't pass this test, but gets AC.

Test:
3 2
2 1 2
2 3 2
2
4 1 0
4 3 0

Wrong Answer: 0
Correct Answer: 2 8

Could somebody tell me, what can be the mistake, if I get WA4?

Anybody knows what in this test?
I've optimized my algorithm after first time limit and now it runs really very fast; on my example file with 100 trains, 100 stations and 100 friends it takes only 145 milliseconds to calculate the answer - even in debug build.
I just cannot imagine why it could calculate answer on some test for more than 2 seconds...
UPD: 129ms in release build...

Edited by author 12.10.2008 04:15

Are there tests like this?
3 4
2 2 1
3 1 7 2
2 1 4

#include<iostream>;

#include<algorithm>;
using namespace std;
//ofstream cout("out.txt");
//ifstream cin("in.txt");
int n,m,i,o,ii,k,l,pp[101],z,a,b,c,ad,kk,nn,mnn=999999999;
int och[101];
bool be[101],bb[101],b1=false;
int bi[101];
bool gr[101][101];
int main()
{
cin>>n>>m;
 for(i=1;i<=m;i++)
 {
 cin>>pp[0];
  for(o=1;o<=pp[0];o++) cin>>pp[o];
  for(o=1;o<=pp[0];o++)
  {
  be[pp[o]]=true;
    for(ii=1;ii<=pp[0];ii++)
    {
    if(pp[ii]!=pp[o]) gr[pp[o]][pp[ii]]=true;
    }
  }
 }
 cin>>k;
 for(i=1;i<=k;i++)
 {
 fill(&bb[1],&bb[100],false);
 fill(&pp[1],&pp[100],0);
 cin>>a>>b>>c;
 och[0]=1;kk=0;
 bb[b]=true;
 pp[b]=0;
 och[1]=b;
 z=0;
 ad=4;
 if (c==1) ad=0;
   while(och[0]>z)
   {
     z+=1;




    for(o=1;o<=n;o++)
    if(gr[och[z]][o] &&(!bb[o])&&(pp[och[z]]+ad<=a))
    {
    bb[o]=true;
    och[0]++;
    och[och[0]]=o;
    pp[o]=pp[och[z]]+ad;
    bi[o]+=pp[o];
    }
   }
 for(o=1;o<=n;o++) be[o]=be[o]&&bb[o];
 }
for(o=1;o<=n;o++)
{
b1=b1||be[o];
if((be[o])&&(bi[o]<mnn))
 {
 nn=o;
 mnn=bi[o];
 }
}
if(!b1) cout<<"0";
else cout<<nn<<" "<<mnn;
return 0;

[code deleted]



Edited by moderator 27.03.2007 09:45

my program work not bad but get WA17. W H Y ???

var
a:array[1..100,1..100] of integer;
b,c,r,money:array[1..100] of integer;
n,m,k,i,j,t,min,p,w:integer;
begin
readln(n,m);
fillchar(a,sizeof(a),$FF);
for i:=1 to m do
begin
read(t);
for j:=1 to t do
read(c[j]);
for j:=1 to t-1 do
for w:=j+1 to t do
a[c[j],c[w]]:=1;
end;
readln(k);
for j:=1 to k do
readln(money[j],b[j],r[j]);
for t:=1 to n do
for i:=1 to n do
for j:=1 to n do
if ((a[i,j]>a[i,t]+a[t,j])or(a[i,j]=-1))and(a[i,t]<>-1)and(a[t,j]<>-1)
then a[i,j]:=a[i,t]+a[t,j];
for i:=1 to n do
a[i,i]:=0;
min:=1000000;p:=0;
for i:=1 to n do
begin
t:=0;
for j:=1 to k do
if (money[j]<a[b[j],i]*4)or(a[b[j],i]=-1) then begin
t:=1000000;
break;
end
else if r[j]=0 then
t:=t+(a[b[j],i])*4;
if t<min then begin
min:=t;
p:=i;
end;
end;
if p=0 then writeln('0')
else writeln(p,' ',min);
end.

if the route is
  3 2 3 1
Can i go from stop 1 to stop 2 ?

I want to know what the test 1 is. thanks.

Edited by author 17.08.2006 15:34

[code deleted]

Edited by moderator 23.02.2006 23:30

Please give me the program now!!

6 3
3 1 2 3
3 4 5 6
3 3 4 6
3
198 1 1
6 3 0
7 3 0
(Test 5)

and why ???