BZOJ 2662: [BJWC2012]冻结 – [分层图最短路]


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

题解 :

分层图最短路模板题

由于K很小, 我们建立K+1层的图,

对于每条边, 除了在每层里都要连一条之外, 在相邻两层之间要连一条权值为\frac{w}{2}的边.

这样, 从第i层走到第i+1层, 相当于使用了一次机会.

特别的, 第K层不一定是最优解, 极限情况当M<K时, 最后一层是更新不到的, 所以我们可以把所有层的n

向下一层的n连一条权值为0的边.

代码 :

BZ少一个特判(Luogu AC)

#include 
#include 
#include 
#include 
#include 
#define P(i, j) ((i-1)*n+j)
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
using namespace std;
char buf[100000], *p1, *p2; const int N = 50*51;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
struct Edge {
    int to, val;
    Edge *next;
}*h[N], e[201000];
inline void addEdge(int u, int v, int w) {
    static int _;
    Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;
}
#define mp make_pair
int n, m, K;
int f[N];
int vis[N];
priority_queue >q;
void Dijkstra() {
    memset(f, 0x3f, sizeof f);
    f[1] = 0;
    q.push(mp(0, 1));
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        rev(i, u) if(f[i->to] > f[u]+i->val) {
            f[i->to] = f[u]+i->val;
            q.push(mp(-f[i->to], i->to));
        }
    }
}
int main() {
    n = rd(), m = rd(), K = rd();
    for(int i = 1; i <= m; i ++ ) {
        int u = rd(), v = rd(), w = rd();
        for(int k = 1; k <= K; k ++ ) {
            addEdge(P(k, u), P(k, v), w);
            addEdge(P(k, v), P(k, u), w);
            addEdge(P(k, u), P(k+1, v), w >> 1);
            addEdge(P(k, v), P(k+1, u), w >> 1);
        }
        addEdge(P(K+1, u), P(K+1, v), w);
        addEdge(P(K+1, v), P(K+1, u), w);
    }
    Dijkstra();
    int ans = 1<<30;
    for(int i = 1; i <= K+1; i ++ ) ans = min(ans, f[P(i, n)]);
    printf("%d\n", ans) ;
}

发表评论

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