[K短路 可持久化堆] HDU 5960 Subsequence

建圖不難 然後直接上K短路 A*被完虐

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define cl(x) memset(x,0,sizeof(x));
using namespace std;
typedef long long ll;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int M=1610005;  
const int N=810005;

struct edge{  
  int u,v,next; ll w;  
}G[M];  
int head[N],inum=1;

inline void add(int u,int v,ll w,int p){  
  G[p].u=u; G[p].v=v; G[p].w=w; G[p].next=head[u]; head[u]=p;  
}

#define V G[p].v
#define U G[p].u

inline int ran(){
  static int x=31253125; x+=(x<<4)+1; return x&65536;
}

struct node{
  node *l,*r; int p;
  bool operator < (const node &B) const{
    return G[p].w<G[B.p].w;
  }
}nodes[(N+M)*20],*root[N];
int ncnt;

inline node *Me(node *A,node *B){
  node *ret=nodes+(++ncnt);
  if (!A || !B) { *ret=A?*A:*B; return ret; }
  if (*B<*A) swap(A,B);
  *ret=*A; ran()?ret->l=Me(A->l,B):ret->r=Me(A->r,B);
  return ret;
}

int S,T;
int m,K;
int ru[M],rv[M],rw[M];
ll dis[N]; int vst[N],nxt[N];
int tag[M];

int lst[N],pnt;

inline void dfs(int u){
  vst[u]=1; lst[++pnt]=u;
  for (int p=head[u];p;p=G[p].next)
    if (!vst[V] && dis[V]==dis[u]+G[p].w)
      tag[p]=1,nxt[V]=u,dfs(V);
}

inline void Build(){
  for (int i=1;i<=pnt;i++){
    int u=lst[i];
    node *last=root[nxt[u]];
    for (int p=head[u];p;p=G[p].next)
      if (!tag[p] && dis[V]!=1<<30){
	++ncnt; nodes[ncnt].l=nodes[ncnt].r=NULL; nodes[ncnt].p=p;
	last=Me(last,nodes+ncnt);
      }
    root[u]=last;    
  }
}

struct abcd{
  ll val; node *last;
  abcd(ll v,node *l) { val=v; last=l; }
  bool operator < (const abcd &B) const{
    return val>B.val;
  }
};

priority_queue<abcd> Q;

ll Ans;
  
inline void Solve(){
  Q.push(abcd(dis[S],NULL));
  for (int i=1;i<=K;i++){
    abcd t=Q.top(); Q.pop();
    if (i==K) { Ans=t.val; break; }
    int v=t.last?G[t.last->p].v:S;
    if (t.last){
      if (t.last->l)
	Q.push(abcd(t.val-G[t.last->p].w+G[t.last->l->p].w,t.last->l));
      if (t.last->r)
	Q.push(abcd(t.val-G[t.last->p].w+G[t.last->r->p].w,t.last->r));
    }
    if (root[v])
      Q.push(abcd(t.val+G[root[v]->p].w,root[v]));
  }
  while (!Q.empty()) Q.pop();
}

int tn;
int a1[N],a2[N],clr[N];
#define P(x,y) ((x)<<1|(y))
int main(){
  int Q;
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(Q);
  while (Q--){
    read(tn); read(K);
    for (int i=1;i<=tn;i++) read(a1[i]),read(a2[i]),read(clr[i]);
    m=0; S=1; T=((tn+1)<<1|1)+1;
    
    ++m; ru[m]=S; rv[m]=P(1,0); rw[m]=0; add(rv[m],ru[m],rw[m],++inum);
    for (int i=1;i<=tn;i++){
      ++m; ru[m]=P(i,0); rv[m]=P(i+1,0); rw[m]=0; add(rv[m],ru[m],rw[m],++inum);
      ++m; ru[m]=P(i,1); rv[m]=P(i+1,1); rw[m]=0; add(rv[m],ru[m],rw[m],++inum);
      ++m; ru[m]=P(i,0); rv[m]=P(i+1,clr[i]); rw[m]=-a1[i]; add(rv[m],ru[m],rw[m],++inum);
      ++m; ru[m]=P(i,1); rv[m]=P(i+1,clr[i]); rw[m]=-a2[i]; add(rv[m],ru[m],rw[m],++inum);
    }
    ++m; ru[m]=P(tn+1,0); rv[m]=T; rw[m]=0; add(rv[m],ru[m],rw[m],++inum);
    ++m; ru[m]=P(tn+1,1); rv[m]=T; rw[m]=0; add(rv[m],ru[m],rw[m],++inum);

    dis[T]=0; for (int i=1;i<T;i++) dis[i]=1<<30;
    for (int i=T;i;i--)
      for (int p=head[i];p;p=G[p].next)
	dis[V]=min(dis[V],dis[i]+G[p].w);
    
    pnt=0; dfs(T);
    for (int i=S;i<=T;i++) head[i]=0; inum=1;
    for (int i=1;i<=m;i++) add(ru[i],rv[i],dis[rv[i]]+rw[i]-dis[ru[i]],++inum);
    Build();
    Solve();
    printf("%lld\n",-Ans);
    for (int i=1;i<=inum;i++) tag[i]=0;
    for (int i=1;i<=T;i++) vst[i]=nxt[i]=0;
    ncnt=0;
    for (int i=S;i<=T;i++) head[i]=0; inum=1;
  }
  return 0;
}