DZY 's BLOG

Safe Travel
Time Limit: 20000 ms Memory Limit: 65536 KB

Description
Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最短路经的长度.
和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i(1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过.没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛棚_i的最短路经是唯一的.
以下是一个牛棚,牛路和时间的例子:

Input
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output
* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

Sample Output
3
3
6

由于题目说了1到没个点的最短路是唯一的。那么这些最短路组成的一棵树-Shortest Path Tree也是唯一的。

dijkstra+heap跑一遍。处理出dist数组。建好SPT。树根当然是1。

对于一个结点u。它的父亲设为p。那么根据题意，从1到u的次短路不能经过<p,u>这条边。

①先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u本身。

②先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u在SPT中的子孙，再沿着SPT上的边就可以走到u了。

考虑给每个节点挂一个可并堆。（二项堆写起来略烦，还是学习了左偏树）

先解决叶子节点u。

叶子节点肯定是上述的第①种情况。

那么把u出发的不是SPT的边<v,u,w>放入一个小根堆中。那么Ans[u]=min{dist[v]+w}。就是堆顶元素。

然后处理非叶子节点u'。

同样，把u'出发的不是SPT的边<v,u',w>放入一个小根堆中。

因为有情况②的存在，所以节点u'的堆要和它所有的儿子v'的堆合并。v'堆合并时要先加上<v',u'>的边权。然后再取出最大值。

为了方便起见，处理节点u时，添加非SPT中的边时，可以把key设为dist[v]+w(v,u)+dist[u]。

如果到了处理u'时取出这个答案的话，Ans[u']=key-dist[u']。（dist[u]-dist[u']就是上述的加上的边权，这样就不用每次合并的时候逐一加了）

还有就是要注意。如果堆顶选出来的这条非SPT边<u,v>，LCA(u,v)在是当前节点的祖先。那就不可行了。这样必定要经过<p,u>边。不合题意。所以不停地删，直到堆顶元素符合。

左偏树中删除堆顶节点的简单办法就是Merge(rt.l,rt.r)了~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 110000,maxm = 510000,inf = 1061109657;
struct node{
    int x,dis;
    node(){};
    node(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (node b)const{
        return dis < b.dis;
    }
}H[maxn];
int pos[maxn]={0},rt[maxm],An[maxn],dfn[maxn],path[maxn],size = 0,ee = 0,cnt = 0;
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn],D[maxn],tot = 0,n,m;
struct lt{
    int l,r,d,id;
}L[maxm];
inline void sw(int a,int b){
    pos[H[a].x] = b;
    pos[H[b].x] = a;
    swap(H[a],H[b]);
}
#define pt (x >> 1)
#define ls (x << 1)
#define rs (x << 1 | 1)
void up(int x){
    if(x == 1)  return;
    if(H[x] < H[pt])    sw(x,pt),up(pt);
}
void down(int x){
    int s = x;
    if(ls <= size && H[ls] < H[x])  s = ls;
    if(rs <= size && H[rs] < H[s])  s = rs;
    if(s != x)  sw(x,s),down(s);
}
void del(int x){
    sw(x,size);
    size --;
    up(x);
    down(x);
}
void ins(node a){
    H[++ size] = a;
    pos[a.x] = size;
    up(size);
}
void dijkstra(int s){
    size = d[s] = 0;
    ins(node(s,0));
    while(size){
        node u = H[1];
        pos[H[1].x] = 0;
        del(1);
        if(vis[u.x])    continue;
        vis[u.x] = 1;
        for(int i = h[u.x];~i;i = n1[i])    if(!vis[p[i]])
            if(u.dis + w[i] < d[p[i]]){
                d[p[i]] = u.dis + w[i];
                path[p[i]] = u.x;
                if(pos[p[i]]){
                    H[pos[p[i]]].dis = d[p[i]];
                    up(pos[p[i]]);
                }else   ins(node(p[i],d[p[i]]));
            }
    }
}
inline void ae(int a,int b,int c){
    p[ee] = b;  w[ee] = c;  n1[ee] = h[a];  h[a] = ee ++;
    p[ee] = a;  w[ee] = c;  n1[ee] = h[b];  h[b] = ee ++;
}
int merge(int a,int b){
    if(!a || !b)    return max(a,b);
    if(L[a].d > L[b].d) swap(a,b);
    L[a].r = merge(L[a].r,b);
    if(D[L[a].r] > D[L[a].l])   swap(L[a].l,L[a].r);
    if(L[a].r == 0) D[a] = 0;
    else     D[a] = D[L[a].r] + 1;
    return a;
}
void dfs(int u,int fa){
    dfn[u] = ++ tot;
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] == u){
            dfs(p[i],u);
            rt[u] = merge(rt[u],rt[p[i]]);
        }
    }
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] != u){
            L[++ cnt] = (lt){0,0,d[u]+w[i]+d[p[i]],p[i]};
            rt[u] = merge(rt[u],cnt);
        }
    }
    while(rt[u] && dfn[L[rt[u]].id] >= dfn[u])
        rt[u] = merge(L[rt[u]].l,L[rt[u]].r);
    An[u] = rt[u] ? L[rt[u]].d - d[u] : -1;
}
    
int main(){
    memset(h,0xff,sizeof(h));
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i = 1;i <= m;i ++){
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);
    }
    memset(d,63,sizeof(d));
    dijkstra(1);
    dfs(1,0);
    for(int i = 2;i <= n;i ++)  printf("%d\n",An[i]);
    return 0;
}

这道题也是分层图。k次机会让边权变0。虽然以前搞过但是好久了我也忘了。于是写死写死地写。然后纠结了下标纠结了n久之后就过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=getint(),e=getint();
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    for(int k=1;k<=K;k++) for(int i=0;i<n;i++) for(int j=h[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]);
        ae(i+(k-1)*n,n*k+p[j],0);
    }dijkstra(s);
    printf("%d\n",d[n*K+e]);
    return 0;
}

n个顶点m条边。给你k次机会让边权减半。一次机会对一条边只能做一次。

n、k都是小于50，那么分层。然后就好了。有些细节比较纠结。于是调了好久。囧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int g[55][55]={0},hh[maxn],h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=1,e=n;
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    memcpy(hh,h,sizeof(h));
    for(int k=1;k<=K;k++) for(int i=1;i<=n;i++) for(int j=hh[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]); 
        ae(i+(k-1)*n,n*k+p[j],w[j]>>1);
    }dijkstra(s); int An=inf; for(int i=0;i<=K;i++) An=min(An,d[n*i+e]);
    printf("%d\n",An); return 0;
}