|
|
вернуться в форумHelp! Why my program got WA? Послано Savior 13 май 2002 22:37 #include<fstream.h> #include<math.h> #define maxn 201 struct Tpoint {double x,y;}; int n,p0,p1,wt; double v1,v2,mint; Tpoint p[maxn],a,b; double w[maxn][maxn]; unsigned char path[maxn][maxn],way[maxn]; double dis(Tpoint g,Tpoint h) { return sqrt((g.x-h.x)*(g.x-h.x)+(g.y-h.y)*(g.y-h.y)); } void init() { int i,j; cin>>v1>>v2>>n; for(i=1;i<=n;i++) cin>>p[i].x>>p[i].y; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) { w[i][j]=dis(p[i],p[j])/v1; w[j][i]=w[i][j]; path[i][j]=0;path[j][i]=0; } do { cin>>i>>j; if(i>0) { w[i][j]=dis(p[i],p[j])/v2; w[j][i]=w[i][j]; } } while(i>0); cin>>a.x>>a.y; cin>>b.x>>b.y; } void pr(int g,int h) { if(path[g][h]==0) return; pr(g,way[wt]); wt++;way[wt]=path[g][h]; pr(way[wt],h); } void print() { int i; cout.setf(ios::fixed); cout.setf(ios::showpoint); cout.precision(7); cout<<mint<<endl; wt=0; if(p0>0) { wt=1;way[1]=p0; pr(p0,p1); wt++;way[wt]=p1; } cout<<wt; for(i=1;i<=wt;i++) cout<<" "<<int(way[i]); cout<<endl; } void scan() { int i,j,k; double u,to[maxn][2]; for(k=1;k<=n;k++) for(i=1;i<n;i++) if(i!=k) for(j=i+1;j<=n;j++) if(j!=k) { u=w[i][k]+w[j][k]; if(u<w[i][j]) { w[i][j]=u;w[j][i]=u; path[i][j]=k;path[j][i]=k; } } for(i=1;i<=n;i++) { to[i][0]=dis(a,p[i])/v1; to[i][1]=dis(b,p[i])/v1; } mint=dis(a,b)/v1; p0=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) { u=to[i][0]+to[j][1]+w[i][j]; if(u<mint) { mint=u; p0=i;p1=j; } } } void main() { init(); scan(); print(); } |
|
|