A * 입문 두 문제 - 제 k 단락 문제 & [SCOI 2005] 기사 정신

A * 알고리즘 은 인터넷 에 자료 가 많아 서 여기 서 쓰 고 싶 지 않 아 요.
가장 중요 한 것 은 평가 함수 f 이 고 현재 상태 에서 최종 상태 까지 의 대 가 를 평가 하 는 것 이다.
진짜 대가 로
진짜.
진짜.
f > f ′, 최선 을 찾 지 못 할 수도 있 지만 빨리 달린다.
질문
그 핵심 은 모든 점 에서 종점 까지 의 최 단 로 를 미리 처리 하 는 것 이다.
g 를 기점 으로 이 점 까지 의 길 이 를 설정 합 니 다.
f = g +h
f 의 크기 에 따라 작은 것 부터 큰 것 까지 쌓 아서 유지 합 니 다.
꺼 낼 때마다 인접 한 점 을 업데이트 합 니 다.
이러한 정확성 은 (일부분 과 같 음) 제 k 단락 길이 보다 작은 경 로 를 모두 찾 았 다 고 상상 할 수 있다. 복잡 도 는 이 재 곱 하기 데이터 구조의 복잡 도 에 달 려 있다.
Code：

#include
#include
#include
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

const int N = 1e4 + 5, M = 2e5 + 5;

int n, m, x, y, z, s, t, k;

struct edge {
    int tt, next[M], to[M], final[N], w[M];
    void link(int x, int y, int z) {next[++ tt] = final[x], to[tt] = y, w[tt] = z, final[x] = tt;}
} e1, e2;

int d[M * 50], dis[N], bz[N];

void Spfa() {
    memset(dis, 127, sizeof dis);
    dis[t] = 0; d[1] = t; d[0] = 1; bz[t] = 1;
    fo(i, 1, d[0]) {
        int x = d[i];
        for(int j = e2.final[x]; j; j = e2.next[j]) {
            int y = e2.to[j], z = e2.w[j];
            if(dis[x] + z < dis[y]) {
                dis[y] = dis[x] + z;
                if(!bz[y]) bz[y] = 1, d[++ d[0]] = y;
            }
        }
        bz[x] = 0;
    }
}

struct node {
    int x, g, h;
    node (int _x, int _g, int _h) {x = _x, g = _g, h = _h;}
    node () {}
};

bool operator return a.g + a.h < b.g + b.h;}

int tot, ts, ans;

multiset st;

int main() {
    scanf("%d %d %d", &n, &m, &k);
    fo(i, 1, m) {
        scanf("%d %d %d", &x, &y, &z);
        e1.link(x, y, z); e2.link(y, x, z);
    }
    s = 1; t = n;
    Spfa();
    st.insert(node(s, 0, dis[s]));
    while(1) {
        ts ++;
        node p = *st.begin();
        int x = p.x;
        if(x == t) {
            if(p.g > ans) tot ++, ans = p.g;
        }
        if(tot == k) {
            printf("%d", p.g); return 0;
        }
        st.erase(st.begin());
        for(int j = e1.final[x]; j; j = e1.next[j]) {
            int y = e1.to[j], z = e1.w[j];
            st.insert(node(y, p.g + z, dis[y]));
        }
    }
}

[SCOI 2005] 기사 정신:
링크
양 방향 광 수 는 넘 을 수 있 을 것 같 지만 상태의 압축 은 좀 번거롭다.
샅 샅 이 뒤 지면 가지치기 만 하면 돼.
현재 상태 에 있 는 걸음 수 를 g 으로 설정 하고 목표 상태 와 다른 수 를 h 로 설정 하면 적어도 h - 1 단계 가 있어 야 도착 할 수 있 습 니 다.
따라서 g + h - 1 > 이미 알 고 있 는 ans 가 있 으 면 물 러 나 면 됩 니 다.
Code：

#include
#include
#include
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

int T, ans;
int move[8][2] = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};
char s[6][6], s2[6][6];

void dg(int g) {
    int sum = 0, x, y;
    fo(i, 1, 5) fo(j, 1, 5) {
        sum += s[i][j] != s2[i][j];
        if(s[i][j] == '*') x = i, y = j;
    }
    if(g + sum > ans) return;
    if(!sum) ans = g;
    fo(i, 0, 7) {
        int l = x + move[i][0], r = y + move[i][1];
        if(l > 0 && l <= 5 && r > 0 && r <= 5) {
            swap(s[l][r], s[x][y]);
            dg(g + 1);
            swap(s[l][r], s[x][y]);
        }
    }
}

int main() {
    freopen("a.in", "r", stdin);

    fo(i, 1, 5) s2[1][i] = '1';
    s2[2][1] = '0'; fo(i, 2, 5) s2[2][i] = '1';
    s2[3][1] = s2[3][2] = '0'; s2[3][3] = '*'; s2[3][4] = s2[3][5] = '1';
    s2[4][5] = '1'; fo(i, 1, 4) s2[4][i] = '0';
    fo(i, 1, 5) s2[5][i] = '0';

    for(scanf("%d", &T); T; T --) {
        fo(i, 1, 5) scanf("%s", s[i] + 1);
        ans = 16;
        dg(0);
        if(ans == 16) printf("-1
"); else printf("%d
", ans);
    }
}