| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:大侠看看呀。。为何过不了啊。。thx+++In Reply To:大侠看看呀。。为何过不了啊。。thx+++ Posted by:782423381 at 2009-10-20 22:41:06 > #include<stdio.h>
> #include<math.h>
> #include<string.h>
> double x[200+10],y[200+10],x11,x22,y11,y22;
> int pos;
> const double INF = 100000000000000 ;
> double d[200+10][200+10],g[200+10][200+10],dd[200+10];
> inline double dis1(const double &a,const double&b,const double &c,const double &d)
> {
> return sqrt((a-c)*(a-c)+(b-d)*(b-d))/1000/40*60;
> }
> inline double dis2(const double &a,const double&b,const double &c,const double &d)
> {
> return sqrt((a-c)*(a-c)+(b-d)*(b-d))/1000/10*60;
> }
> /*int floyd( int n)
> {
> int i,j,k;
> for (k =0; k <n; k ++ )
> {
> for (i = 0 ; i < n; i ++ )
> for (j = 0 ; j <n; j ++ )
> {
> if (d[i][k] < INF && d[k][j] < INF&& d[i][k] + d[k][j] < d[i][j])
> d[i][j] = d[i][k] + d[k][j];
> }
> }
> printf("%.0f\n",d[0][n-1]);
> return 0 ;
> }*/
> void Dijkstra(int n,int v,double *Dist) //或int Dist[MAX];
> {
> double Cost[200+10][200+10];
> memcpy(Cost,d,sizeof(Cost));
> double temp,newdist;
> int i,j,u;
> bool s[200+10];
> for(i=0;i<n;i++) Cost[i][i]=0;
> for(i=0;i<n;i++)
> {
> Dist[i]=Cost[v][i];
> s[i]=false;
> }
>
> Dist[v]=0;
> s[v]=true;
>
> for(i=1;i<n;i++)
> {
> temp=INF;
> //u=v;
> for(j=0;j<n;j++)
> {
> if((!s[j]) && (Dist[j]<temp))
> {
> u=j; temp=Dist[j];
> }
> }
> s[u]=true;
> for(j=0;j<n;j++)
> {
> if((!s[j]))// && (Cost[u][j]<MAXVALUE))
> {
> newdist=Dist[u]+Cost[u][j];
> if(newdist<Dist[j]) Dist[j]=newdist;
> }
> }
> }
> printf("%.0lf",Dist[n-1]);
> return ;
> }
>
> void process()
> {
> int i,j;
> double t1,t2;
> for(i=0,pos=0;i<200+10;i++)
> for(j=0;j<200+10;j++) d[i][j]=INF;
> x[pos]=x11,y[pos++]=y11;
> while(scanf("%lf%lf",&t1,&t2)==2)
> {
> if(t1==-1&&t2==-1) continue;
> x[pos]=t1,y[pos++]=t2;
> while(true)
> {
> scanf("%lf%lf",&t1,&t2);
> if(t1==-1&&t2==-1) break;
> x[pos]=t1,y[pos]=t2;
> d[pos][pos-1]=d[pos-1][pos]=dis1(x[pos],y[pos],x[pos-1],y[pos-1]);
> ++pos;
> }
> }
> x[pos]=x22,y[pos++]=y22;
> for(i=0;i<pos;i++)
> for(j=i+1;j<pos;j++)
> {
> double xxx=dis2(x[i],y[i],x[j],y[j]);
> if(xxx<d[i][j]) d[i][j]=xxx;
> }
> // floyd(pos);
> Dijkstra(pos,0,dd);
> }
> int main()
> {
> //freopen("in.txt","r",stdin);
> //freopen("out.txt","w",stdout);
> while(scanf("%lf%lf%lf%lf",&x11,&y11,&x22,&y22)==4) process();
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator