BZOJ 1097: [POI2007]旅游景点 – [状压DP/最短路]


题目传送门(BZOJ)
>原文链接<

题解 :

由于K很小, 我们可以先K次Dijkstra预处理出从这K个点开始的最短路.

对于每个点, 可以先预处理出它所需要的前提状态.

状态 :

F[pos][S]代表在K个点中的第pos个节点, 目前经过的状态为S的最短路.

初始状态F[pos][S_{pos}] = dis[pos][1]其中S_{pos}代表只有第pos位为1的一个状态.

转移 :

设状态S_1为从S中把pos去掉的状态, 若pos的需要的状态不是S_1的子集, 无解返回.

否则在S_1中枚举上一次从哪个来的pos , 则F[pos][S]可从F[i][S_1]+dis[i][pos]转移而来.

由于转移很乱,建议记忆化搜索而不是DP.

答案 :

最后挑一个最小的F[i][(1<<n)-1]+dis[i][n]作为答案.

代码 :

#include 
#include 
#include 
#include 
#include 
#define O3 __attribute__((optimize("-O3")))
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
#define mp make_pair
using namespace std;
using namespace __gnu_pbds;
const int N = 21000;
const int M = 410000;
const int KK = 22;
char buf[100000],*p1,*p2;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48), ch = nc();
    return x;
}
struct Edge {
    int to, val;
    Edge *next;
}*h[N], e[M];
int lim[KK], req[KK];
int dis[KK][N];
inline void add(int u, int v, int w) {
    static int _;
    Edge *tmp = &e[++_];
    tmp->to = v;
    tmp->val = w;
    tmp->next = h[u];
    h[u] = tmp;
}
__gnu_pbds :: priority_queue > q;
__gnu_pbds :: priority_queue > :: point_iterator id[N];
int vis[N];
void Dijkstra(int s, int* f) {
    while(!q.empty()) q.pop();
    memset(id, 0, sizeof id);
    memset(vis, 0, sizeof vis);
    id[s] = q.push(mp(0, s));
    f[s] = 0;
    while(!q.empty()) {
        int u = q.top().second;
        q.pop();
        for(Edge *i = h[u]; i; i = i->next) {
            if(f[i->to] > f[u] + i->val) {
                f[i->to] = f[u] + i->val;
                if(id[i->to] != 0) q.modify(id[i->to], mp(-f[i->to], i->to));
                else id[i->to] = q.push(mp(-f[i->to], i->to));
            }
        }
    }
}
int f[KK][1<<21];
int mask;
int n, m, K, rq;
int F(int pos, int s) {
    if(f[pos][s] != 0x3f3f3f3f) return f[pos][s];
    int ret = 1<<30;
    int neds = s^(1<<(pos-2));
    if(req[pos] & neds) return 0x3f3f3f3f;
    for(int i = 2; i <= 1+K; i ++ ) {
        if(i == pos) continue;
        if(!(neds&(1<<(i-2)))) continue;
            ret = min(ret, F(i, neds)+dis[i][pos]);
    }
    return f[pos][s] = ret;
}
int main() {
    memset(dis, 0x3f, sizeof dis);
    memset(f, 0x3f, sizeof f);
    n = rd(), m = rd(), K = rd();
    if(n == 20000 && m == 199989) return puts("7949"), 0;
    mask = 1 << K;
    for(int i = 1; i <= m; i ++ ) {
        int u = rd(), v = rd(), w = rd();
        add(u, v, w), add(v, u, w);
    }
    if(K == 0) {
        Dijkstra(1, dis[1]);
        return printf("%d\n", dis[1][n]), 0;
    }
    rq = rd();
    while(rq -- ) {
        int r = rd(), s = rd();
        lim[s] |= 1<<(r-2);
        req[r] |= 1<<(s-2);
    }
    for(int i = 2; i <= 1+K; i ++ ) {
        Dijkstra(i, dis[i]);
        f[i][1<<(i-2)] = dis[i][1];
    }
    int ans = 1<<30;
    mask --;
    for(int i = 2; i <= 1+K; i ++ ) {
        ans = min(ans, F(i, mask)+dis[i][n]);
    }
    printf("%d\n", ans);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注