Subway

POJ-2502

这里除了直接相连的地铁站，其他图上所有的点都要连线，这里是走路的速度。
记住最后的结果需要四舍五入，否则出错。
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

using namespace std;

typedef pair<int,int> p;

const int INF=0x3f3f3f3f;

int sx,sy,ex,ey;

struct edge{

    int to;

    double cost;

    int next;

};

struct node{

    double dis;

    int to;

    node(){}

    node(int a,int b):dis(a),to(b){}

    bool operator<(const node& t)const{

        return dis>t.dis;

    }

};

edge ma[1500005];

int head[220];

int top;//指向头结点

double d[220];

int tn;//结点个数

int n=220;//最大结点数

map<pair<int,int>,int> mmap;

map<int,pair<int,int> >mmap1;

void addedge(int a,int b,double c){

    ma[top].to=b;

    ma[top].cost=c;

    ma[top].next=head[a];

    head[a]=top;

    top++;

}

void dijikstra(int s){

    priority_queue<node> que;

    for(int i=0;i<tn;i++){

        d[i]=INF;

    }

    d[s]=0;

    que.push(node(0,s));

    while(!que.empty()){

        node temp=que.top();

        que.pop();

        int v=temp.to;

        if(d[v]<temp.dis)

            continue;

        for(int h=head[v];h!=-1;h=ma[h].next){

            edge e=ma[h];

            if(d[e.to]>d[v]+e.cost){

                d[e.to]=d[v]+e.cost;

                que.push(node(d[e.to],e.to));

            }

        }

    }

}

bool isnode(int x,int y){

    if(!mmap.count(p(x,y))){

        mmap1[tn]=p(x,y);

        mmap[p(x,y)]=tn++;

        return true;

    }else return false;

}

double G[220][220];

int main(){

    memset(head,-1,sizeof(head));

    top=0;

    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);

    mmap1[tn]=p(sx,sy);

    mmap[p(sx,sy)]=tn++;//0

    mmap1[tn]=p(ex,ey);

    mmap[p(ex,ey)]=tn++;//1

    int x,y;

    while(scanf("%d%d",&x,&y)!=EOF){

        int nx,ny;

        if(!mmap.count(p(x,y))){

            mmap1[tn]=p(x,y);

            mmap[p(x,y)]=tn++;

        }

        while(scanf("%d%d",&nx,&ny)!=EOF&&(nx!=-1||ny!=-1)){

            if(!mmap.count(p(nx,ny))){

                mmap1[tn]=p(nx,ny);

                mmap[p(nx,ny)]=tn++;

            }

            double distance=sqrt((nx-x)*(nx-x)+(ny-y)*(ny-y));

            distance/=40000.0;

            int ttn=mmap[p(nx,ny)];

            int ttnp=mmap[p(x,y)];

            addedge(ttn,ttnp,distance);

            addedge(ttnp,ttn,distance);

            G[ttn][ttnp]=distance;

            G[ttnp][ttn]=distance;

            x=nx,y=ny;

        }

    }

    for(int i=0;i<tn;i++){

        for(int j=0;j<tn;j++){

            if(G[i][j]==0&&i!=j){

                p p1=mmap1[i];

                sx=p1.first,sy=p1.second;

                p p2=mmap1[j];

                ex=p2.first,ey=p2.second;

                double distance1=sqrt((ex-sx)*(ex-sx)+(ey-sy)*(ey-sy));

                distance1/=10000.0;

                addedge(i,j,distance1);

                G[i][j]=distance1;

            }

        }

    }

    dijikstra(0);

    int final=d[1]*60.0+0.5;

    cout<<final<<endl;

    //system("pause");

    return 0;

}
巴特西

POJ-2502(Dijikstra应用+最短路)

Subway

POJ-2502

最新文章

热门文章
