POJ - 2502 Subway 专门儿恶心人的最短路模版（内附一纠错数据）

本文主要是介绍POJ - 2502 Subway 专门儿恶心人的最短路模版（内附一纠错数据），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

POJ-2502

题意

给定若干条地铁线路，起点坐标和终点坐标，你可以选择走路或者坐地铁，铁路40km/h，走路10km/h。问起点到终点最短时间。

解法

裸的单源最短路，强调几个点。

输入是坐标，建一个结构体储存，之后再一一对应成节点
因为两种方式速度不同，dis数组不要存放距离，存放时间，边的权也设置为时间。
步行可以取两点之间距离计算时间，地铁不可以，因为地铁有固定行进路线，只有相邻两站之间是可以用地理距离计算时间的。下附一极端数据：

输入
0 0 1000 0
0 0 0 1000000 1000 1000000 1000 0 -1 -1

正确输出
6（步行到终点）

错误输出
2（全程坐车并且直接用始末站直线距离计算时间）
注意换算，坐标是m，速度是km/h，输出是min。
注意输出格式，四舍五入，可以用（int）ans+0.5或者round()函数
double型初始化别用memset，for循环慢慢搞吧，可以自己试试memset 0x3f和-1的情况。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>  
#include<cmath>
#include<cstdio>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;typedef pair <double,int> P;const int maxn=35005;const int maxe=155005;const int inf=0x3f3f3f3f;int head[maxn];struct Node{double x,y;}node[maxn];struct Edge{int to;int next;double w;} edge[maxe];int cnt,node_cnt;double dis[maxn];//存放距离 bool vis[maxn];//是否在队列 int in[maxn];//更新了多少次 void init(){memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i=0;i<maxn;i++)dis[i]=inf;cnt=0;}inline void add(int u,int v,double w){edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].w=w;head[u]=cnt;cnt++;}bool spfa(int s) {queue<int>q;q.push(s);vis[s]=true;in[s]++;dis[s]=0;while(q.size()) {int p=q.front();q.pop();vis[p]=false;for(int i=head[p];i!=-1;i=edge[i].next) { //SPFAint v=edge[i].to;if(dis[v]>edge[i].w+dis[p]) {dis[v]=edge[i].w+dis[p];in[v]++; if(!vis[v]) {vis[v]=true;q.push(v);}}}}return false;}double getdis(int i,int j){return sqrt((node[i].x-node[j].x)*(node[i].x-node[j].x)+((node[i].y-node[j].y)*(node[i].y-node[j].y)));}int main(){IOSinit();cin>>node[1].x>>node[1].y>>node[2].x>>node[2].y;double x,y;double a[1000],b[1000];int p,n=3;node_cnt=3;while(cin>>x>>y){p=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));a[p]=x,b[p++]=y;cin>>x>>y;while(x!=-1&&y!=-1){a[p]=x,b[p++]=y;cin>>x>>y;}for(int i=0;i<p;i++)node[node_cnt].x=a[i],node[node_cnt++].y=b[i];int i=0;while(i+1<p){add(n+i,n+i+1,getdis(n+i,n+i+1)*3/2000.0);add(n+i+1,n+i,getdis(n+i,n+i+1)*3/2000.0);i++;}n+=p;	}for(int i=1;i<node_cnt;i++)for(int j=1;j<node_cnt;j++)add(i,j,getdis(i,j)*6/1000.0);spfa(1);int ans=dis[2]+0.5;cout<<ans<<endl;return 0;}