$$\color{Purple}{kuangbin题解目录}$$
描述
你每天早上都要从家赶往学校。
你可以选择步行或者乘坐地铁赶路。
你的步行速度是 $10$ 千米/小时,地铁的行驶速度是 $40$ 千米/小时。
假设你足够幸运,任何时刻你抵达任何地铁站,都能赶上一个立即发车的地铁。
你可以多次上下地铁,也可以随意换乘不同地铁线路。
所有地铁线路都是双向的。
请你计算,你在路中需要花费的最少时间。
输入格式
第一行输入你的家和学校位置的 $x,y$ 坐标。
随后若干行,每行描述一条地铁线路。按线路顺序输出每个线路中包含的所有站点的 $x,y$ 坐标。地铁在相邻站点之间沿直线行驶,坐标均表示整数米,每条线路至少包含两个站点,所有站点坐标输入结束后,行末会跟有虚拟坐标 -1 -1
。
输出格式
输出你到学校所需的最少分钟数。四舍五入取整。
数据范围
输入所有坐标均为整数。
输入中最多包含 $200$ 个站点。
输入样例:
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
输出样例:
21
思路
单源最短路问题
,求从起点家
出发到达学校
的最短路径,该题的难点在于如何建图
,剩下的套板子即可;- 对于
地铁
来说,每相邻两站
需要建边,而并不是一组内的所有点都需要建边;- 对于
步行
来说,每个点(包括起点和终点)
都应该建立边;- 存储的结果应该是分钟($min$),由于该题的速度($km/h$)和点的坐标($m$)
单位不统一
,需要转化成相同单位,假设两点间的曼哈顿距离
为$dist$米,地铁的速度$v$为$40km/h=\frac{40,000}{60} m/min=\frac{2,000}{3} m/min$,故两点之间地铁的时间为$\frac{dist}{v}=\frac{dist\times 3}{2,000} min$,同理步行的速度$v$为$10km/h=\frac{10,000}{60} m/min=\frac{500}{3} m/min$,故两点之间步行的时间为$\frac{dist}{v}=\frac{dist\times 3}{500} min$;- 此题亦可采用$floyd$算法解决,点的数量不算太多.
代码
- $Dijkstra$(朴素版)
// Problem: 地铁
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4251/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-27 13:18:16
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 210
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
PII point[MAXN];
int vis[MAXN];
double dist[MAXN],val[MAXN][MAXN];
int cnt=3;//1,2存储起点终点坐标
double get_dist(PII a,PII b)
{
int x1=a.first,x2=b.first,y1=a.second,y2=b.second;
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void dijkstra(int start)
{
for(int i=1;i<=cnt;i++)
dist[i]=inf;
dist[start]=0;
for(int i=1;i<cnt;i++)
{
int pos=-1;
for(int j=1;j<=cnt;j++)
if(vis[j]==0&&(pos==-1||dist[j]<dist[pos]))
pos=j;
//最短路跑到2证明当前已经是最短的,后面的松弛改变不了结果
if(pos==2)
break;
vis[pos]=1;
for(int j=1;j<=cnt;j++)
dist[j]=min(dist[j],dist[pos]+val[pos][j]);
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
for(int i=1;i<MAXN;i++)
for(int j=1;j<MAXN;j++)
{
if(i==j)
val[i][j]=0;
else val[i][j]=inf;
}
cin >> point[1].first >> point[1].second >> point[2].first >> point[2].second;
int flag=0;
int x,y;
while(cin >> x >> y)
{
if(x==-1&&y==-1)
{
flag=0;
continue;
}
//point[cnt]={x,y};
point[cnt]=make_pair(x,y);
if(flag==1)
val[cnt][cnt-1]=val[cnt-1][cnt]=get_dist(point[cnt],point[cnt-1])*3/2000;
flag=1;
cnt++;
}
cnt--;
//处理步行
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
val[i][j]=val[j][i]=min(val[i][j],get_dist(point[i],point[j])*3/500);
dijkstra(1);
printf("%.0f\n",dist[2]);
return 0;
}
- $Dijkstra$(堆优化版)
// Problem: 地铁
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4251/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-27 13:18:16
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 210
#define MAXM 50010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,int> PDI;
const int inf=0x3f3f3f3f;
PII point[MAXN];
int vis[MAXN];
double dist[MAXN];
int cnt=3;//1,2存储起点终点坐标
int head[MAXN],ed[MAXM],nex[MAXM],idx;
double val[MAXM];
void add(int a,int b,double c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
double get_dist(PII a,PII b)
{
int x1=a.first,x2=b.first,y1=a.second,y2=b.second;
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void dijkstra(int start)
{
for(int i=1;i<=cnt;i++)
dist[i]=inf;
dist[start]=0;
priority_queue<PDI,vector<PDI>,greater<PDI> > q;
q.push({0,start});
//q.push(make_pair(0,start));
while(q.size()>0)
{
PDI temp=q.top();
q.pop();
double temp_dis=temp.first;
int temp_pos=temp.second;
if(temp_pos==2)
break;
if(vis[temp_pos]==1)
continue;
vis[temp_pos]=1;
for(int i=head[temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[j]>temp_dis+val[i])
{
dist[j]=temp_dis+val[i];
q.push({dist[j],j});
//q.push(make_pair(dist[j],j));
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
memset(head,-1,sizeof(head));
cin >> point[1].first >> point[1].second >> point[2].first >> point[2].second;
int flag=0;
int x,y;
while(cin >> x >> y)
{
if(x==-1&&y==-1)
{
flag=0;
continue;
}
point[cnt]={x,y};
//point[cnt]=make_pair(x,y);
if(flag==1)
{
double temp=get_dist(point[cnt],point[cnt-1])*3/2000;
add(cnt,cnt-1,temp);
add(cnt-1,cnt,temp);
}
flag=1;
cnt++;
}
cnt--;
//处理步行
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
{
double temp=get_dist(point[i],point[j])*3/500;
add(i,j,temp);
add(j,i,temp);
}
dijkstra(1);
printf("%.0f\n",dist[2]);
return 0;
}
- $spfa$
// Problem: 地铁
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4251/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-27 13:18:16
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 210
#define MAXM 50010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,int> PDI;
const int inf=0x3f3f3f3f;
PII point[MAXN];
int vis[MAXN];
double dist[MAXN];
int cnt=3;//1,2存储起点终点坐标
int head[MAXN],ed[MAXM],nex[MAXM],idx;
double val[MAXM];
void add(int a,int b,double c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
double get_dist(PII a,PII b)
{
int x1=a.first,x2=b.first,y1=a.second,y2=b.second;
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void spfa(int start)
{
for(int i=1;i<=cnt;i++)
dist[i]=inf;
dist[start]=0;
queue<int> q;
q.push(start);
vis[start]=1;
while(q.size()>0)
{
int temp=q.front();
q.pop();
vis[temp]=0;
for(int i=head[temp];i!=-1;i=nex[i])
{
int j=ed[i];
if(dist[j]>dist[temp]+val[i])
{
dist[j]=dist[temp]+val[i];
if(vis[j]==0)
{
vis[j]=1;
q.push(j);
}
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
memset(head,-1,sizeof(head));
cin >> point[1].first >> point[1].second >> point[2].first >> point[2].second;
int flag=0;
int x,y;
while(cin >> x >> y)
{
if(x==-1&&y==-1)
{
flag=0;
continue;
}
point[cnt]={x,y};
//point[cnt]=make_pair(x,y);
if(flag==1)
{
double temp=get_dist(point[cnt],point[cnt-1])*3/2000;
add(cnt,cnt-1,temp);
add(cnt-1,cnt,temp);
}
flag=1;
cnt++;
}
cnt--;
//处理步行
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
{
double temp=get_dist(point[i],point[j])*3/500;
add(i,j,temp);
add(j,i,temp);
}
spfa(1);
printf("%.0f\n",dist[2]);
return 0;
}
- $floyd$
// Problem: 地铁
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4251/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-27 13:18:16
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 210
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
PII point[MAXN];
double val[MAXN][MAXN];
int cnt=3;//1,2存储起点终点坐标
double get_dist(PII a,PII b)
{
int x1=a.first,x2=b.first,y1=a.second,y2=b.second;
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void floyd()
{
for(int k=1;k<=cnt;k++)
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
val[i][j]=min(val[i][j],val[i][k]+val[k][j]);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
for(int i=1;i<MAXN;i++)
for(int j=1;j<MAXN;j++)
{
if(i==j)
val[i][j]=0;
else val[i][j]=inf;
}
cin >> point[1].first >> point[1].second >> point[2].first >> point[2].second;
int flag=0;
int x,y;
while(cin >> x >> y)
{
if(x==-1&&y==-1)
{
flag=0;
continue;
}
//point[cnt]={x,y};
point[cnt]=make_pair(x,y);
if(flag==1)
val[cnt][cnt-1]=val[cnt-1][cnt]=get_dist(point[cnt],point[cnt-1])*3/2000;
flag=1;
cnt++;
}
cnt--;
//处理步行
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
val[i][j]=val[j][i]=min(val[i][j],get_dist(point[i],point[j])*3/500);
floyd();
printf("%.0f\n",val[1][2]);
return 0;
}