题目：输入x1,y1,x2,y2表示起点和终点的坐标。接下来输入地铁线
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1 起点(0,0),终点（10000，1000）第一条地铁线是（0，200）--（5000，200）--（7000，200）第二条是--------------------------（自己看）文件结束输入哦主角是可以从任意点走到任意点的，速度是10000/60，坐地铁的话不用等，速度是40000/60；地铁是可以在中间站下车的例如（0，200）这样的点。
双向的，而且两个相邻中间站的中间站之间是直线问：从起点到终点的最快时间思路:建图很重要，主角可以从起点走到终点，也可以从地铁的中间站上车。 要注意,假如有个地铁线路，我或许从第二个站台下车，直接走到第四个站台更快，所以当存地铁线路时候，当前站台（如果不是第一个)和上一个站台建立速度为40000/60的地铁线，而和上上个站台或许更上个站台建立速度为10000/60的路。注意double
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <
string>
#include <map>
#include <iomanip>
#include <algorithm>
#include <queue>
#pragma GCC optimize(3)
#include <stack>
#include <
set>
#include <vector>
//const int maxn = 1e5+5;
#define ll long long
ll gcd(ll a,ll b){return b?gcd(b,a%
b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*
b;}
//const int inf = 0x6fffffff;
const double INF=
1e30;
#define MAX INT_MAX
#define FOR(i,a,b) for( int i = a;i <= b;++i)
#define bug cout<<"--------------"<<endl
using namespace std;
const int v1 =
10000/
60,v2 =
40000/
60;
int ver[
110000],next[
110000],head[
110000],vis[
110000];
double d[
110000],edge[
110000];
struct node
{
int x,y;
}p[510];
int tot,tail;
void add(
int x,
int y,
double z)
{
//cout<<x<<" "<<y<<" "<<z<<endl;
ver[++tot] = y,edge[tot] = z,next[tot] = head[x],head[x] =
tot;
}
void makeload(
int x,
int y,
int temp,
int flag)
{
for(
int i=
1;i<=temp;i++
)
{
double len = (x - p[i].x)*(x - p[i].x) + (y - p[i].y)*(y -
p[i].y);
len =
sqrt(len);
len = len /
v1;
add(tail,i,len);
add(i,tail,len);
}
if(flag ==
1)
return ;
double len = (x - p[tail-
1].x)*(x - p[tail-
1].x) + (y - p[tail-
1].y)*(y - p[tail-
1].y);
len =
sqrt(len);
len = len/
v2;
add(tail,tail-
1,len);
add(tail-
1,tail,len);
}
void dijistre()
{
priority_queue<pair<
double,
int> >
que;
for(
int i=
1;i<=tot;i++
)
{
d[i]=
999999;
//cout<<d[i]<<endl;
}
d[1] =
0;
que.push(make_pair(0,
1));
while(que.size())
{
int x =
que.top().second;
que.pop();
if(vis[x] ==
1)
continue;
vis[x] =
1;
for(
int i=head[x];i;i=
next[i])
{
int y =
ver[i];
double z =
edge[i];
if(d[y] > d[x] +
z)
{
d[y] = d[x] +
z;
que.push(make_pair(-
d[y],y));
}
}
}
}
int main()
{
//ios::sync_with_stdio(false);cout.tie(0);
int hx,hy,sx,sy;
cin>>hx>>hy>>sx>>
sy;
double len = (hx - sx)*(hx - sx) + (hy - sy)*(hy -
sy);
len =
sqrt(len);
len = len/
v1;
add(1,
2,v1);
add(2,
1,v1);
p[++tail].x = hx,p[tail].y =
hy;
p[++tail].x = sx,p[tail].y =
sy;
int x,y;
while(scanf(
"%d%d",&x,&y)!=EOF)
//读入地铁
{
int temp = tail;
//zhunque
p[++tail].x = x,p[tail].y =
y;
makeload(x,y,tail-
1,
1);
while(scanf(
"%d%d",&x,&y)!=
EOF)
{
if(x == -
1 && y == -
1)
break;
p[++tail].x =
x;
p[tail].y =
y;
makeload(x,y,tail-
2,
2);
}
}
dijistre();
cout<<
fixed<<setprecision(
0)<<d[
2]<<
endl;
}
转载于:https://www.cnblogs.com/jrfr/p/11371063.html
相关资源：JAVA上百实例源码以及开源项目
