桂林做手机网站建设宝坻网站建设制作

题意：给出起点终点坐标，然后给出可以经过的几个点，未经过这几个点的时候以v1的速度前进，一旦经过这些点就可以在3秒内以v2的速度前进，3秒之后恢复v1，问从起点到终点所需的最短时间

思路：最短路模型没什么好说的，如果采用邻接表方式存图建边会比较麻烦，很遗憾我就是用的邻接表，注意从起点出发的点只能以v1的速度前进

ac代码：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int N=1010;
pii _point[N];
int n;
double dist[N];
bool vis[N];
pii _start,_end;
vector<pair<int,double>> g[N];
double v1,v2;
double getdist(int sx,int sy,int tx,int ty)
{return sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty));
}
double gettime(pii a,pii b,bool isv2)//isv2代表是否加速
{double len=getdist(a.first,a.second,b.first,b.second);double time;if(isv2){time=len/v2;if(time>3)time=3+(time-3)*v2/v1;}else time=len/v1;return time;
}
void dij()
{priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> q;dist[n]=0;q.push({dist[n],n});while(q.size()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;q.push({dist[v],v});}}}
}
void solve()
{cin>>n;for(int i=0;i<=n+1;i++)dist[i]=1e9;for(int i=0;i<n;i++)cin>>_point[i].first>>_point[i].second;//将0加速点到n-1加速点的坐标存下来cin>>_start.first>>_start.second>>_end.first>>_end.second;//起点和终点的坐标cin>>v1>>v2;//假设起点为n,终点为n+1for(int i=0;i<n;i++){for(int j=0;j<n;j++)//对于每个加速点都向其他加速点以连一条边{g[i].pb({j,gettime(_point[i],_point[j],true)});}g[i].pb({n+1,gettime(_point[i],_end,true)});//再从每个点向终点连一条边}for(int i=0;i<n;i++)//从起点处发的边都是未加速的{g[n].pb({i,gettime(_start,_point[i],false)});//从起点向每个加速点连一条边}g[n].pb({n+1,gettime(_start,_end,false)});//从起点到终点连一条边dij();printf("%.12lf\n",dist[n+1]);
}
signed main()
{Mirai;int T=1;// cin>>T;while(T--){solve();}
}