题解：P1027 [NOIP 2001 提高组] Car 的旅行路线
Vector_net · · 题解
本题属于计算几何题，建议搭配草稿纸食用。
看见这句话：“找出一条从城市 A 到 B 的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。”我们便可以考虑最短路。
Part-1 建边：
简单理解一下题意，我们发现这张图的边只有两种：城市中间的高铁边与连接城市的飞机边。边权分别是
这时，一个问题来了，我们只知道矩形的三个点，如何计算第四个点？实际上，这个问题十分简单，只要找到矩形上那个两线垂直的顶点，则有另外两个点的中点与该顶点与未知点的中点相同，由此即可计算了。而垂直可以使用
好了，于是，现在我们只需要对一个城市的四个点进行枚举并建边，再枚举每个城市，嵌套枚举四个点建边即可。
Part-2 计算答案：
建好边后，我们可以使用 SPFA 算法计算最短路，这道题目数据极小，显然是不会被卡的。为了方便，我们用超级源点与超级汇点连接 A、B 中的每个点，这样就可以直接刷 SPFA 算法了。
Part-3 Show the code.
#include <bits/stdc++.h>
using namespace std;
const int maxn=405,maxe=400005;
const double INF=1e100;
int T,n,t,A,B,tot,son[maxe],nxt[maxe],lnk[maxn],que[maxn];
double w[maxe],dis[maxn];
bool vis[maxn];
struct ZYX{
int x[5],y[5],w;
}a[105];
inline int read(){//快读
int ret=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline double slope(int a,int b,int c,int d){//计算斜率
if(a==c)return INF;//特判斜率不存在
return (double)(b-d)/(a-c);
}
inline double Get(int a,int b,int c,int d){return sqrt((a-c)*(a-c)+(b-d)*(b-d));}//计算两点间距离
inline void add_e(int x,int y,double z){son[++tot]=y,w[tot]=z,nxt[tot]=lnk[x],lnk[x]=tot;}//建边，这里使用链式前向星存图
inline double spfa(){//简单易懂的SPFA算法
for(int i=0;i<maxn;i++)dis[i]=INF;
int hed=0,til=1;
que[1]=0,vis[0]=1,dis[0]=0;
while(hed!=til){
hed=(hed+1)%maxn;vis[que[hed]]=0;
for(int j=lnk[que[hed]];j;j=nxt[j]){
if(dis[que[hed]]+w[j]>=dis[son[j]])continue;
dis[son[j]]=dis[que[hed]]+w[j];
if(!vis[son[j]]){vis[son[j]]=1;til=(til+1)%maxn;que[til]=son[j];}
int now=(hed+1)%maxn;
if(dis[que[now]]>dis[que[til]])swap(que[now],que[til]);
}
}
return dis[4*n+1];
}
int main(){
T=read();
while(T--){
n=read(),t=read(),A=read(),B=read();
memset(lnk,0,sizeof lnk);tot=0;//初始化
for(int i=1;i<=n;i++){
a[i].x[1]=read(),a[i].y[1]=read();
a[i].x[2]=read(),a[i].y[2]=read();
a[i].x[3]=read(),a[i].y[3]=read();
if(slope(a[i].x[1],a[i].y[1],a[i].x[2],a[i].y[2])*slope(a[i].x[1],a[i].y[1],a[i].x[3],a[i].y[3])==0&&(slope(a[i].x[1],a[i].y[1],a[i].x[2],a[i].y[2])==INF||slope(a[i].x[1],a[i].y[1],a[i].x[3],a[i].y[3])==INF)||slope(a[i].x[1],a[i].y[1],a[i].x[2],a[i].y[2])*slope(a[i].x[1],a[i].y[1],a[i].x[3],a[i].y[3])==-1)a[i].x[4]=-a[i].x[1]+a[i].x[2]+a[i].x[3],a[i].y[4]=-a[i].y[1]+a[i].y[2]+a[i].y[3];
if(slope(a[i].x[1],a[i].y[1],a[i].x[2],a[i].y[2])*slope(a[i].x[2],a[i].y[2],a[i].x[3],a[i].y[3])==0&&(slope(a[i].x[1],a[i].y[1],a[i].x[2],a[i].y[2])==INF||slope(a[i].x[2],a[i].y[2],a[i].x[3],a[i].y[3])==INF)||slope(a[i].x[1],a[i].y[1],a[i].x[2],a[i].y[2])*slope(a[i].x[2],a[i].y[2],a[i].x[3],a[i].y[3])==-1)a[i].x[4]=-a[i].x[2]+a[i].x[1]+a[i].x[3],a[i].y[4]=-a[i].y[2]+a[i].y[1]+a[i].y[3];
if(slope(a[i].x[3],a[i].y[3],a[i].x[2],a[i].y[2])*slope(a[i].x[1],a[i].y[1],a[i].x[3],a[i].y[3])==0&&(slope(a[i].x[3],a[i].y[3],a[i].x[2],a[i].y[2])==INF||slope(a[i].x[1],a[i].y[1],a[i].x[3],a[i].y[3])==INF)||slope(a[i].x[3],a[i].y[3],a[i].x[2],a[i].y[2])*slope(a[i].x[1],a[i].y[1],a[i].x[3],a[i].y[3])==-1)a[i].x[4]=-a[i].x[3]+a[i].x[2]+a[i].x[1],a[i].y[4]=-a[i].y[3]+a[i].y[2]+a[i].y[1];
//计算第四个点的位置
a[i].w=read();
}
add_e(0,4*(A-1)+1,0);add_e(0,4*(A-1)+2,0);
add_e(0,4*(A-1)+3,0);add_e(0,4*(A-1)+4,0);
add_e(4*(B-1)+1,4*n+1,0);add_e(4*(B-1)+2,4*n+1,0);
add_e(4*(B-1)+3,4*n+1,0);add_e(4*(B-1)+4,4*n+1,0);
//建立源点与汇点
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int M=i==j?a[i].w:t;
for(int p=1;p<=4;p++)
for(int q=1;q<=4;q++)add_e(4*(i-1)+p,4*(j-1)+q,Get(a[i].x[p],a[i].y[p],a[j].x[q],a[j].y[q])*M);
}
}
//建边，由于枚举中包含了i=j的情况，因此包含了城内情况
printf("%.1lf\n",spfa());//输出答案，完美收尾！
}
return 0;
}