题目: 输入 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;
- }
来源: http://www.bubuko.com/infodetail-3160226.html