After unsuccefull attemts to pass 10-test
I write maximal common ineffective program
of full search of all simple paths in graph and
againg have Wa10.
Are somebody can find bugs in next code?
#include<vector>
#include<iostream>
#include<set>
#include<stdio.h>
using namespace std;
struct reb{
char v;
char c;
int h;
int t;
int nm;
};
struct ver{
char num;
int mon;//spended money duriing echiving of vertex
int len;//path-length
vector<int>path;//rebs in path
set<int>path1;//simple vertex path
};
struct reb Smeg[100][10000];
int Nr[100],s,N,M,t0,money,maxtime;
int ff(int hh,vector<int>&p)//1- hh can be used, 0-cannot for echiving t0 from s
{
struct ver vv,vv1;
int m,i,j,ii;
vector<struct ver>S1,S2;//levels for BST
set<int>::iterator pp;
struct reb rr;
vv.num=s;//buiding root of BST
vv.mon=0;vv.len=0;
vv.path1.insert(s);
vv.path.clear();
S1.push_back(vv);//Building BST step by step from level to level
while (S1.size()>0)
{//0
S2.clear();
for (i=1;i<=S1.size();i++)
{
vv=S1[i-1];
if ((vv.num==t0)&&(vv.len<=maxtime)&&(vv.mon<=money)) {p=vv.path;return 1;}//to is ehived succsefully
m=vv.num;//building next level
for (ii=1;ii<=Nr[m-1];ii++)
{//4
rr=Smeg[m-1][ii-1];
if (rr.h<=hh)//reb r can be used under this condition only
{//5
pp=vv.path1.find(rr.v);//verifing of simplicity of the path to vertex
if (pp==vv.path1.end())
{//7
vv1.len=vv.len+rr.t;
if (rr.c==1) vv1.mon=vv.mon+1;else vv1.mon=vv.mon;
vv1.num=rr.v;
if ((vv1.mon<=money)&&(vv1.len<=maxtime))
{//6
vv1.path=vv.path;
vv1.path1=vv.path1;
vv1.path.push_back(rr.nm);
vv1.path1.insert(rr.v);
S2.push_back(vv1);
}//6
}//7
}//5
}//4
}//3
S1=S2;
}//0
return 0;
}
int main()
{
int i,q ,u,p,z,hh1,hh2,hh,m,k,j;
struct reb r;
vector<int>pp;
scanf("%d%d%d%d%d%d",&N,&M,&s,&t0,&money,&maxtime);
for (i=1;i<=N;i++) Nr[i-1]=0;
hh2=0;hh1=1000000;
for (i=1;i<=M;i++)
{
scanf("%d%d%d%d%d",&u,&q,&p,&j,&k);
r.t=j;r.h=k;
if (u==q) goto aa;//scip loops
hh2=max(hh2,r.h);hh1=min(hh1,r.h);
r.v=q;r.c=p;r.nm=i;
Nr[u-1]++;
Smeg[u-1][Nr[u-1]-1]=r;
r.v=u;
Nr[q-1]++;
Smeg[q-1][Nr[q-1]-1]=r;
aa:;
}//binary search
if (ff(hh1,pp)==1)goto bb;
if (ff(hh2,pp)==0) {cout<<-1;return 0;}
while (hh2>hh1)
{
if (hh2-hh1==1) {i=ff(hh2,pp);hh1=hh2;break;}
hh=(hh1+hh2)/2;
if (ff(hh,pp)==1) hh2=hh;else hh1=hh;
}
bb:
//output
cout<<hh1<<endl;
cout<<pp.size()<<endl;
for (i=1;i<=pp.size();i++) cout<<pp[i-1]<<endl;
return 0;
}
Edited by author 30.07.2007 11:18 Edited by author 30.07.2007 11:18