企业网站建设公司网络,企业cms wordpress,静态网站建设的PPT,只建设电子商务网站不维护题意#xff1a;给出起点终点坐标#xff0c;然后给出可以经过的几个点#xff0c;未经过这几个点的时候以v1的速度前进#xff0c;一旦经过这些点就可以在3秒内以v2的速度前进#xff0c;3秒之后恢复v1#xff0c;问从起点到终点所需的最短时间
思路#xff1a;最短路…题意给出起点终点坐标然后给出可以经过的几个点未经过这几个点的时候以v1的速度前进一旦经过这些点就可以在3秒内以v2的速度前进3秒之后恢复v1问从起点到终点所需的最短时间
思路最短路模型没什么好说的如果采用邻接表方式存图建边会比较麻烦很遗憾我就是用的邻接表注意从起点出发的点只能以v1的速度前进
ac代码
#includebits/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 pairint,int pii;
const int N1010;
pii _point[N];
int n;
double dist[N];
bool vis[N];
pii _start,_end;
vectorpairint,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 lengetdist(a.first,a.second,b.first,b.second);double time;if(isv2){timelen/v2;if(time3)time3(time-3)*v2/v1;}else timelen/v1;return time;
}
void dij()
{priority_queuepairdouble,int,vectorpairdouble,int,greaterpairdouble,int q;dist[n]0;q.push({dist[n],n});while(q.size()){int uq.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()
{cinn;for(int i0;in1;i)dist[i]1e9;for(int i0;in;i)cin_point[i].first_point[i].second;//将0加速点到n-1加速点的坐标存下来cin_start.first_start.second_end.first_end.second;//起点和终点的坐标cinv1v2;//假设起点为n,终点为n1for(int i0;in;i){for(int j0;jn;j)//对于每个加速点都向其他加速点以连一条边{g[i].pb({j,gettime(_point[i],_point[j],true)});}g[i].pb({n1,gettime(_point[i],_end,true)});//再从每个点向终点连一条边}for(int i0;in;i)//从起点处发的边都是未加速的{g[n].pb({i,gettime(_start,_point[i],false)});//从起点向每个加速点连一条边}g[n].pb({n1,gettime(_start,_end,false)});//从起点到终点连一条边dij();printf(%.12lf\n,dist[n1]);
}
signed main()
{Mirai;int T1;// cinT;while(T--){solve();}
}
