几何+最短路dijkstra
枚举每两个点, 判断能否不受阻碍的直线抵达, 如果可以便加入邻接矩阵
判断能否直线相连的时候再次暴力枚举就行了
最后是直接模板的dij
个人感觉构图有点烦, 可能是写的少的原因吧
/*poj1556-dijkstra author:birdstorm*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>#define MAXN 1005
#define N 105
#define inf 1.0e9
#define INF 1<<30
#define eps 1.0e-8#define For(i,m,n) for(i=(m);i<(n);i++)
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))typedef struct{double x;double y;
}point;point p[25][6];
double dist[N], g[N][N];
int vis[N];
int n;double cha(point p1,point p0,point p2)
{return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}double dis(int start, int num1, int end, int num2)
{double tx, ty;tx=p[end][num2].x-p[start][num1].x;ty=p[end][num2].y-p[start][num1].y;return sqrt(tx*tx+ty*ty);
}int judge_access(int start, int num1, int end, int num2)
{int i, j;For(i,start+1,end){For(j,0,3){if(cha(p[start][num1],p[i][j*2],p[end][num2])*cha(p[start][num1],p[i][j*2+1],p[end][num2])<eps) return 0;}}return 1;
}void graph()
{int i, j, k, m;For(i,0,4*n+2) For(j,0,4*n+2) g[i][j]=inf;if(judge_access(0,0,n+1,0)){g[0][4*n+1]=10; return;}For(k,1,n+1){For(m,1,5){if(judge_access(0,0,k,m)) g[0][k*4+m-4]=dis(0,0,k,m);}}For(i,1,n+1){For(j,1,5){For(k,i,n+1){For(m,1,5){if(judge_access(i,j,k,m)) g[i*4+j-4][k*4+m-4]=dis(i,j,k,m);}}if(judge_access(i,j,n+1,0)) g[i*4+j-4][n*4+1]=dis(i,j,n+1,0);}}/*/For(i,0,4*n+2){For(j,0,4*n+2) printf("%.2lf ",g[i][j]);printf("\n");}//*/
}void dijkstra()
{int i, j, mark;double mindis;For(i,1,4*n+2) dist[i]=inf;dist[0]=0;memset(vis,0,sizeof(vis));For(i,0,4*n+2){mark=-1, mindis=1.0e20;For(j,0,4*n+2) if(!vis[j]&&dist[j]<mindis){mindis=dist[j];mark=j;}vis[mark]=1;For(j,0,4*n+2) if(!vis[j]) dist[j]=MIN(dist[j],g[mark][j]+dist[mark]);//For(j,0,4*n+2) printf("%.2lf ",dist[j]);}}main()
{int i, j, k, t;double x;while(scanf("%d",&n),n!=-1){For(i,1,n+1){scanf("%lf",&x);For(j,0,6) p[i][j].x=x;For(j,1,5) scanf("%lf",&p[i][j].y);p[i][0].y=0; p[i][5].y=10;}p[0][0].x=0; p[0][0].y=5;p[n+1][0].x=10; p[n+1][0].y=5;graph();dijkstra();printf("%.2lf\n",dist[4*n+1]);}return 0;
}