计算几何 + 图论，线段相交判定 + 最短路径算法。
考虑如何建图？将图中线段的每一个端点，起始点和终点作为图中的边，考察对于任意节点i和节点j，如果i和j之间没有墙，则建立一条长度为几何距离的边，否则不建立边。
如何判断i和j之间是否有墙？创建一条起点为i终点为j的线段，遍历全部的墙（线段），利用计算几何的方法，判断线段是否相交即可。建图完成后，
运行从开始点到终点的Dijkstra算法即可，源代码见下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const double inf = 1e20;
const double eps = 1e-8;
const double pi = acos(-1);
int cmp (double a, double b) {
    if(fabs(a - b) < 0) {
        return 0;
    }
    if(a > b) {
        return 1;
    } else {
        return -1;
    }
}
double add(double a, double b) {
    if(abs(a + b) < eps * (abs(a) + abs(b))) {
        return 0;
    }
    return a + b;
}
struct P {
    double x, y;
    P() {}
    P(double x, double y): x(x), y(y) {}
    P operator + (P p) {
        return P(add(x, p.x), add(y, p.y));
    }
    P operator - (P p) {
        return P(add(x, -p.x), add(y, -p.y));
    }
    P operator * (double d) {
        return P(x * d, y * d);
    }
    double operator * (P p) {
        return add(x * p.x, y * p.y);
    }
    double operator ^ (P p) {
        return add(x * p.y, -y * p.x);
    }
    double dist(P p) {
        return sqrt( (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y) );
    }
};
struct L {
    P s, e;
    L() {}
    L(double a, double b, double c, double d) : s(a, b), e(c, d) {}
    L(P s, P e): s(s.x, s.y), e(e.x, e.y) {}
    bool on(P p) {
        return ((p - s) ^ (p - e)) == 0 && ((p - s) * (p - e)) <= 0;
    }
    P intersection(L l) {
        return s + (e - s) * (((l.s - l.e) ^ (s - l.s)) / ((l.s - l.e) ^ (s - e)));
    }
    bool cross(L l) {
        P p = intersection(l);
        return on(p) && l.on(p);
    }
};
char buf[1024];
vector<P> arr_P;
vector<L> arr_L;
struct edge {
    int to;
    double d;
};

typedef pair<double, int> Node;
vector<edge> G[2048];
double dist[2048];

int N;
int V;

double dijkstra() {
    fill(dist, dist + V, inf);
    priority_queue<Node, vector<Node>, greater<Node> > que;
    dist[0] = 0;
    que.push(Node(0, 0));
    while(!que.empty()) {
        Node p = que.top();
        que.pop();
        int v = p.second;
        if(dist[v] < p.first) {
            continue;
        }
        for(int i = 0; i < G[v].size(); i ++) {
            edge & e = G[v][i];
            if(dist[e.to] > dist[v] + e.d) {
                dist[e.to] = dist[v] + e.d;
                que.push(Node(dist[e.to], e.to));
            }
        }
    }
    return dist[V - 1];
}

int main() {
    while(true) {
        scanf("%d", &N);
        getchar();
        if(N == -1) {
            break;
        }
        arr_P.clear();
        arr_L.clear();
        for(int i = 0; i < 2048; i ++) {
            G[i].clear();
        }
        arr_P.push_back(P(0, 5));
        for(int i = 0; i < N; i ++) {
            gets(buf);
            int index = 0;
            int len = strlen(buf);
            double loc;
            sscanf(buf,"%lf", &loc);
            while(index < len && buf[index] != ' ') {
                index ++;
            }
            index ++;
            double a, b;
            sscanf( buf + index,"%lf", &a);
            arr_P.push_back(P(loc, a));
            arr_L.push_back(L(loc, 0, loc, a));
            while(index < len) {
                while(index < len && buf[index] != ' ') {
                    index ++;
                }
                index ++;
                if(index < len) {
                    sscanf( buf + index, "%lf", &a);
                }
                while(index < len && buf[index] != ' ') {
                    index ++;
                }
                index ++;
                if(index >= len) {
                    arr_P.push_back(P(loc, a));
                    arr_L.push_back(L(loc, a, loc, 10));
                } else {
                    sscanf(buf + index, "%lf", &b);
                    arr_P.push_back(P(loc, a));
                    arr_P.push_back(P(loc, b));
                    arr_L.push_back(L(loc, a, loc, b));
                }
            }
        }
        arr_P.push_back(P(10, 5));
        V = arr_P.size();
        for(int i = 0; i < V; i ++) {
            for(int j = i + 1; j < V; j ++) {
                if(arr_P[j].x == arr_P[i].x) {
                    continue;
                }
                L line(arr_P[i], arr_P[j]);
                bool able = true;
                for(int k = 0; k < arr_L.size(); k ++) {
                    if(arr_L[k].s.x > arr_P[i].x && arr_L[k].s.x < arr_P[j].x) {
                        if(line.cross(arr_L[k])) {
                            able = false;
                            break;
                        }
                    }
                }
                if(able) {
                    edge e;
                    e.to = j;
                    e.d = arr_P[i].dist(arr_P[j]);
                    G[i].push_back(e);
                }
            }
        }
        printf("%.2f\n", dijkstra());
    }
}

• Re:500题，0ms，1A留念！！第500题献给了 图论+计算几何，留下详解以留念 (5492) link_hy 2019-06-27 09:52:28