题解 P2443 【[SDOI2005]高速公路】
首先，根据题目意思，显然最短路径有一个性质：只在节点处转弯
于是我们考虑枚举每一对点，算出它们之间走直线的距离，然后跑最短路就可以了。
那么，该怎么求最短路呢？
最短路可以用 空地走过的总长度*u0+四边形内花费的总价值计算
对于凸四边形，一条线段（注意线段！！）和它至多有两个交点，所以我们直接找出线段和凸四边形的所有交点并去重，如果刚好剩下两个交点直接算距离和代价了，否则线段和多边形没有交点。
（注意：线段和四边形的交点如果是四边形两个相邻的顶点，也当做无交点处理）
对于凹四边形，可以找出它大于180度的角，并沿这个角的顶点所在的对角线将它分为两个三角形，接着就是和凸四边形一样的做法了。
（注意：被分开的三角形原本有一条边是在四边形内的，如果线段和三角形共这条边，不能当做无交点处理，共其它边则可以当做无交点处理）
处理完每一对距离，就可以直接跑最短路了，复杂度是 (4n)^3 的，我的代码由于stl用的太多，加上写的太丑，所以开O2才过的去。
考场代码改了改：
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define d(i,j) ((i-1)*4+j+3)
#define P pair<ld,int>
using namespace std;
typedef long double ld;
const ld eps=1e-4,inf=1e12;
const int N=415,M=200010;
int ppp=0;
ld dt[N],w[M],f[M],dis[N],g[N];
int n,s=1,t=2,siz[N],vis[N],fst[N],nxt[M],u[M],v[M],tot;//siz:单个图形中点的数量
bool del[N],fl[N];//del:四边形被割开后被删掉（移走）的点，fl：被割开的那条边经过的点（对应注意2）
priority_queue<P > q;
struct aa
{
ld x,y;
bool operator <(const aa &b)const{return fabs(x-b.x)<eps? y<b.y:x<b.x;}
bool operator ==(const aa &b)const{return fabs(x-b.x)+fabs(y-b.y)<eps;}
aa operator +(const aa &b)const{return aa{x+b.x,y+b.y};}
aa operator -(const aa &b)const{return aa{x-b.x,y-b.y};}
aa operator *(const ld &b)const{return aa{x*b,y*b};}
ld operator *(const aa &b)const{return x*b.x+y*b.y;}
ld operator ^(const aa &b)const{return x*b.y-y*b.x;}
ld len() {return sqrt(x*x+y*y);}
void read() {scanf("%Lf%Lf",&x,&y);}
}pt[N];
struct bb {aa s,t;};
void add(int lu,int lv,ld lw,ld lf)
{
u[++tot]=lu,v[tot]=lv,w[tot]=lw,f[tot]=lf,nxt[tot]=fst[lu],fst[lu]=tot;
u[++tot]=lv,v[tot]=lu,w[tot]=lw,f[tot]=lf,nxt[tot]=fst[lv],fst[lv]=tot;
}
bool px(bb a,bb b) {return fabs((b.t-b.s)^(a.t-a.s))<eps;} //判断平行
aa crs(bb a,bb b) {return b.s+(b.t-b.s)*(((b.s-a.s)^(a.t-a.s))/((a.t-a.s)^(b.t-b.s)));} //求交点
bool inn(bb a,aa b) {return fabs((b-a.s).len()+(b-a.t).len()-(a.t-a.s).len())<eps;} //判断是否在直线上
ld work2(bb a,int b)
{
int i,j,fll=0,lf=-1;
aa lg;
vector<aa> pp;
for(i=0;i<siz[b];i++)
{
bb lx=bb{pt[d(b,i)],pt[d(b,(i+1)%siz[b])]};
if(px(lx,a)) continue;
aa lp=crs(lx,a);
if(inn(lx,lp)&&inn(a,lp)) pp.push_back(lp);
}
sort(pp.begin(),pp.end());
for(i=0;i<pp.size();i++)
{
if(i&&pp[i]==pp[i-1]) continue;
for(j=0;j<siz[b];j++)
if(pt[d(b,j)]==pp[i])
if(lf==-1) lf=j;
else if(abs(j-lf)!=2||siz[b]==3&&(!fl[d(b,j)]||!fl[d(b,lf)])) return 0;
if(!fll) fll=1,lg=pp[i];
else return (lg-pp[i]).len();
}
return 0;
}//求一条线段和四边形（三角形）的公共部分
void work(int a,int b)
{
int i,j;
ld len=(pt[b]-pt[a]).len(),res=0;
bb lp=bb{pt[a],pt[b]};
for(i=1;i<=n;i++)
{
ld lx=work2(lp,i);
res+=dt[i]*lx,len-=lx;
}
res+=dt[0]*len,add(a,b,res,(pt[b]-pt[a]).len());
}//加边
void dj()
{
int i,j;
for(i=1;i<N;i++) dis[i]=inf,vis[i]=0;
dis[s]=0,g[s]=0,q.push(P(0,s));
while(!q.empty())
{
int lx=q.top().second;
q.pop();
if(vis[lx]) continue;
vis[lx]=1;
for(i=fst[lx];i;i=nxt[i])
if(dis[v[i]]>dis[lx]+w[i]+eps) dis[v[i]]=dis[lx]+w[i],g[v[i]]=g[lx]+f[i],q.push(P(-dis[v[i]],v[i]));
}
}//最短路
int main()
{
int i,j;
ld res=0;
pt[s].read(),pt[t].read(),scanf("%Lf%d",&dt[0],&n);
for(i=n;i;i--)
{
siz[i]=4;
scanf("%Lf",&dt[i]);
for(j=0;j<4;j++) pt[d(i,j)].read();
res+=((pt[d(i,2)]-pt[d(i,1)])^(pt[d(i,0)]-pt[d(i,1)]))/2+((pt[d(i,0)]-pt[d(i,3)])^(pt[d(i,2)]-pt[d(i,3)]))/2;
for(j=0;j<4;j++)
{
bb lp=bb{pt[d(i,(j+3)%4)],pt[d(i,j)]},lq=bb{pt[d(i,j)],pt[d(i,(j+1)%4)]};
if(((lp.t-lp.s)^(lq.t-lq.s))<0)//凹四边形
{
n++,del[d(i,3)]=del[d(n,3)]=1,siz[n]=siz[i]=3,dt[n]=dt[i];
fl[d(n,0)]=fl[d(n,2)]=1;
pt[d(n,0)]=pt[d(i,j)],pt[d(n,1)]=pt[d(i,(j+1)%4)],pt[d(n,2)]=pt[d(i,(j+2)%4)];
if(j==3) pt[d(i,0)]=pt[d(i,1)],pt[d(i,1)]=pt[d(i,2)],pt[d(i,2)]=pt[d(i,3)],fl[d(i,0)]=fl[d(i,2)]=1;
if(j==0) pt[d(i,1)]=pt[d(i,2)],pt[d(i,2)]=pt[d(i,3)],fl[d(i,0)]=fl[d(i,1)]=1;
if(j==1) pt[d(i,2)]=pt[d(i,3)],fl[d(i,1)]=fl[d(i,2)]=1;
if(j==2) fl[d(i,2)]=fl[d(i,0)]=1;
break; //凹四边形新建一个三角形，并将原来的图形也变成三角形
}
}
}
for(i=1;i<=d(n,3);i++)
for(j=i+1;j<=d(n,3);j++)
if(!del[i]&&!del[j]) work(i,j);
dj();
printf("%.2Lf\n%.2Lf\n%.2Lf",res,g[t],dis[t]);
return 0;
}