BZOJ 2763/1579: [JLOI2011]飞行路线 – [分层图最短路]


题目传送门(BZOJ)

题解 :

K很小,考虑分层图

把用掉一次免费机会视作走到下一层, 先建出来K+1层图, 对于每条边, 从层i到层i+1连接权为0的单向边

对于所有层的n(T),向下一层的对应T连一条0权边

这两道题的区别就是从ST还是从1n没什么大的不一样.

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define mp(a,b) make_pair(a,b)
#define sec second
const int N = 20000;
const int M = 60000;
struct node {
    int next, to, val;
}e[(M<<1)*60];
int n, m, k;
int cnt, head[N*31];
int dis[N*31];
void add_edge(int a, int b, int c) {
    e[++cnt].to = b;
    e[cnt].val = c;
    e[cnt].next = head[a];
    head[a] = cnt;
}
int s, t;
priority_queue, vector >, greater > >q;
bool vis[N*31];
void Dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(mp(0, s));
    while(!q.empty()) {
        int u = q.top().sec;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i = e[i].next) {
            if(dis[e[i].to]>dis[u]+e[i].val) {
                dis[e[i].to] = dis[u]+e[i].val;
                q.push(mp(dis[e[i].to], e[i].to));
            }
        }
    }
    printf("%d\n", dis[n*k+t]);
}
int main() {
    scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
    for(int i = 1; i <= m; i ++ ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        for(int j = 0; j <= k; j ++ ) {
            add_edge(b+j*n, b+j*n, 0);
            add_edge(a+j*n, a+j*n, 0);
            add_edge(b+j*n, a+j*n, c);
            add_edge(a+j*n, b+j*n, c);
            add_edge(b+j*n, a+(j+1)*n, 0);
            add_edge(a+j*n, b+(j+1)*n, 0);
        }       
    }
    Dijkstra();
}

发表评论

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