Zigzag

ACM-ICPC 2008 Aizu, Problem J: Zigzag

解説の通り Dijkstra で解いてみました。 与えられた点を通る２つの直線の組み合わせについて、交点を求め, その交点と入力された点の集合について TSP を解くような感じです。 状態は S[現在の点(入力された点のみ)][前にいた点][通った点の状態(入力された点のみ)] になります。

ただし、無駄な交点を作ってしまうとTLEになります。

コードは, Dijkstra の部分のみです。

void dijkstra(){
    priority_queue<QState> PQ[5];
    bool C[10][MAX][SMAX];
    rep(i, nnode) rep(j, n) rep(k, (1<<nnode)) C[i][j][k]= false;

    rep(s, nnode) rep(i, P[s].size) {
        int v = P[s].adj[i].t;
        if ( v < nnode ){
            PQ[0].push(QState(S[s]|S[v], v, s, 0, P[s].adj[i].d));
        } else {
            rep(j, P[v].size){
                int vv = P[v].adj[j].t;
                if ( vv == s ) continue;
                int nt = CCW2[s][v][vv]; 
                PQ[nt].push(QState(S[s]|S[vv], vv, v, nt, P[s].adj[i].d + P[v].adj[j].d));
            }
        }
    }

    QState u;
    while(1){
        u = getState(PQ);
        if ( u.state == S[nnode]-1 ) {
            printf("%d %.5lf\n", u.nturn, u.dist);
            return;
        }
        if ( C[u.cur][u.pre][u.state] ) continue;
        C[u.cur][u.pre][u.state] = true;

        int p0 = u.pre;
        int p1 = u.cur;
        int p2, p3;

        rep(i, P[p1].size){
            int p2 = P[p1].adj[i].t;
            double ndist = P[p1].adj[i].d;
            if ( p2 < nnode ){
                ushort state = (u.state|S[p2]);
                ushort nt = u.nturn + CCW1[p0][p1][p2];
                if ( nt >= 5 ) continue;
                double nd = u.dist + ndist;
                if ( !C[p2][p1][state] ) PQ[nt].push(QState(state, p2, p1, nt, nd));
            } else {
                rep(j, P[p2].size ){
                    p3 = P[p2].adj[j].t;
                    if ( p3 == p1 ) continue;
                    ushort state = (u.state|S[p3]);
                    ushort nt = u.nturn + CCW1[p0][p1][p2] + 1;
                    if ( nt >= 5 ) continue;
                    double nd = u.dist + ndist + P[p2].adj[j].d;
                    if ( !C[p3][p2][state] ) PQ[nt].push(QState(state, p3, p2, nt, nd));
                }
            }
        }
    }
}