Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

最后输出要四舍五入,否则会WA ,附上AC代码

Posted by huozhiwei at 2014-12-06 15:05:02 on Problem 2502
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 1<<22
using namespace std;
int used[550];
double dis[550];
double map[550][550];
int t;
struct point
{
    double x,y;
}p[550];
void dijkstra()
{
    memset(used,0,sizeof(used));
    for(int i=1;i<t;i++)
    dis[i]=map[0][i];
    dis[0]=0;
    used[0]=1;
    int k;
    double minn;
    for(int i=1;i<t;i++)
    {
        minn=inf;
        for(int j=1;j<t;j++)
        {
            if(!used[j]&&dis[j]<minn)
            {
                minn=dis[j];
                k=j;
            }
        }
        used[k]=1;
        for(int j=1;j<t;j++)
        {
            if(!used[j]&&dis[j]>dis[k]+map[k][j])
            dis[j]=map[k][j]+dis[k];
        }
    }
    cout<<int(60.0*dis[1]+0.5)<<endl;//四舍五入
}
double d(double x1,double y1,double x2,double y2)
{
    double temp=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    return temp;
}
int main()
{
    t=2;
    int flag=0;
    cin>>p[0].x>>p[0].y>>p[1].x>>p[1].y;
    memset(map,0.0,sizeof(map));
    while(cin>>p[t].x>>p[t].y)
    {
        if(p[t].x==-1&&p[t].y==-1)
        {
            flag=0;
            continue;
        }
        if(flag)
        {
            double temp=d(p[t].x,p[t].y,p[t-1].x,p[t-1].y)/40000.0;
            map[t][t-1]=map[t-1][t]=temp;
        }
        flag=1;
        t++;
    }
    for(int i=0;i!=t;i++)
    for(int j=0;j!=t;j++)
    {
        if(i!=j&&map[i][j]==0.0)
        map[i][j]=map[j][i]=d(p[i].x,p[i].y,p[j].x,p[j].y)/10000.0;
    }
    dijkstra();
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator