題意：給出起點終點坐標，然后給出可以經過的幾個點，未經過這幾個點的時候以v1的速度前進，一旦經過這些點就可以在3秒內以v2的速度前進，3秒之后恢復v1，問從起點到終點所需的最短時間

思路：最短路模型沒什么好說的，如果采用鄰接表方式存圖建邊會比較麻煩，很遺憾我就是用的鄰接表，注意從起點出發(fā)的點只能以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++)//從起點處發(fā)的邊都是未加速的{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();}
}