[POI2007]ATR-Tourist Attractions

题目大意：一个无向图，从$1$到$n$，要求必须经过$2,3,\dots,k+1$，给出一些限制关系，要求在经过$v\leq k+1$之前必须经过$u\leq k+1$，求最短路

题解：预处理出$1\dots k+1$到其他点的最短路，然后$f_{s,i}$表示当前在$i$已经经过的点的集合为$s$（压位）的最短路，然后$DP$就行了（原题卡内存，但我不大会啊，但在不卡内存的$bzoj$上过了）

卡点：1.$\&$优先级比$==$低

C++ Code：

#include <cstdio>

#include <cstring>

#include <ext/pb_ds/priority_queue.hpp>

#define maxn 20002

#define maxm 200002

#define maxk 20

using namespace std;

const int inf = 0x3f3f3f3f;

int n, m, k, g, ans, st;

int head[maxn], cnt;

struct Edge {

    int to, nxt, w;

} e[maxm << 1];

void add(int a, int b, int c) {

    e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;

}

int f[1 << maxk][maxk + 2], d[maxk + 2][maxn], s[maxk + 2];

struct cmp {

    bool operator () (const int &a, const int &b) const {

        return d[st][a] > d[st][b];

    }

};

inline int min(int a, int b) {return a < b ? a : b;}

__gnu_pbds::priority_queue<int, cmp> q;

__gnu_pbds::priority_queue<int, cmp>::point_iterator iter[maxn];

void dijkstra(int S) {

    st = S;

    for (int i = 1; i <= n; i++) d[S][i] = inf, iter[i] = q.push(i);

    d[S][S] = 0;

    q.modify(iter[S], S);

    while (!q.empty()) {

        int u = q.top(); q.pop();

        for (int i = head[u]; i; i = e[i].nxt) {

            int v = e[i].to;

            if (d[S][v] > d[S][u] + e[i].w) {

                d[S][v] = d[S][u] + e[i].w;

                q.modify(iter[v], v);

            }

        }

    }

}

int main() {

    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i++) {

        int a, b, c;

        scanf("%d%d%d", &a, &b, &c);

        add(a, b, c);

        add(b, a, c);

    }

    memset(f, 0x3f, sizeof f);

    scanf("%d", &g);

    for (int i = 1; i <= g; i++) {

        int a, b;

        scanf("%d%d", &a, &b);

        s[b] |= 1 << a - 2;

    }

    for (int i = 1; i <= k + 1; i++) dijkstra(i);

    if (!k) {

        printf("%d\n", d[1][n]);

        return 0;

    }

    f[0][1] = 0;

    for (int i = 2; i <= k + 1; i++) if (!s[i]) f[1 << i - 2][i] = d[1][i];

    for (int i = 0; i < 1 << k; i++) {

        for (int j = 0; j < k; j++) {

            if (i & 1 << j) {

                for (int l = 0; l < k; l++) {

                    if ((~i & 1 << l) && ((i & s[l + 2]) == s[l + 2])) {

                        f[i | 1 << l][l + 2] = min(f[i | 1 << l][l + 2], f[i][j + 2] + d[j + 2][l + 2]);

                    }

                }

            }

        }

    }

    ans = inf;

    for (int i = 2; i <= k + 1; i++) ans = min(ans, f[(1 << k) - 1][i] + d[i][n]);

    printf("%d\n", ans);

    return 0;

}

巴特西

[POI2007]ATR-Tourist Attractions

最新文章

热门文章