我的算法是先枚举每条线跟别的线的交点.
然后求出交点的坐标,由其得出中点坐标,就是门的位置.
构图的时候map[i][j]表示门i和门j能否连通,并默认连通的距离是1;
0号点连接所有在边界上可直达的点,目标点定为maxn+1.
最后用dijkstra求0到maxn+1的点的最短路.
因为线最多为30,加四边为34.
所以交点最多为(n+1)*n/2,中点数为(n+1)*n/2-n
因为n<=34所以门的总数maxn<=561.
然后做一次o(n^2)的最短路.
怎么会超时的呢?
是我的算法有问题,还是我写的时候没写好,造成了死循环?
如果我的算法没问题,那我再重新写一遍好了,
如果是算法问题,求教更好的算法.

• Re:求教怎么会超时. (92) wings 2008-05-11 14:41:00