JDFZ 2978 제 K 단락 지구 화 더미 + A * 사상

링크
방법: 더미 + A * 사상 을 지속 적 으로 유지 할 수 있 습 니 다.
해석:
원래 의 A * 알고리즘 은 BFS 와 동급 이 라 고 합 니까?
그래서 K 단락 은 누 드 A * 가 O (n * k) 급 인가요?
이 문제 는
1<=n<=10000,1<=m<=100000,1<=k<=10000
그래서 누 드 A * 는 폭발 이 야.
고려 하여 최적화 하 다.
여기 서 운용 하 는 최적화 방법 은 모두 유정 리 황소 가 pdf 에서 언급 한 사상 이다.
PDF 링크
우선, 전체 그림 에 대해 우 리 는 각 점 에서 n 까지 의 가장 짧 은 경로 트 리 를 구 합 니 다.
그래서?
(내 가 각 점 에서 n 까지 의 최 단 경로 트 리 를 구 하 는 것 을 주의 하 세 요. 그래서 변 은 반대 입 니 다)
한 변 의 가중치 를 이 변 의 to 의 최 단 경로 값 으로 정의 하고 이 변 의 from 의 최 단 경로 값 을 빼 고 이 변 의 변 권 을 추가 합 니 다.
솔직히 이 거 는 이쪽 으로 가면 돌아 가 는 거 리 를 말 하 는 거 예요?
이렇게 정 의 된 후에 우 리 는 모든 변 의 값 을 다시 부여 합 니 다.
그래서 어떻게 할 까요?
첫 번 째 우회 거 리 는 분명히 0 이다.
모든 상태 에서 한 무더기 씩 열 어 라.
한 상 태 는 두 부분 이 있다.
첫 번 째 부분 은 이미 몇 거 리 를 돌 았 는 지, 두 번 째 부분 은 어떤 상태 로 옮 길 수 있 는 지.
키 값 은 어떤 상태 에서 돌아 가 는 거리 와 이 상태 에서 쌓 인 더미 의 최소 돌아 가 는 거리 입 니 다.
그리고 분명히 매번 우 리 는 이 작은 뿌리 더미 의 지붕 을 가 져 간다.
그리고 옮 길 수 있 는 상 태 를 작은 뿌리 더미 에 던진다.
이렇게 k 회 를 반복 하면 k 단락 에서 얼마나 거 리 를 돌 았 는 지 계산 할 수 있 고 마지막 에 가장 짧 은 거 리 를 더 하면 된다.
이제 보 니 옮 겨 진 점 마다 다음 에 옮 길 수 있 는 변 은 조상 들 의 모든 점 에서 옮 길 수 있 는 변 이라는 것 을 알 게 되 었 다.
그 러 니까 이 부분 은 우리 가 나 무 를 만들어 서 함부로 기록 하면 돼.
그 다음 에 이것 은 하나의 문제 와 관련 되 는데 그것 이 바로 모든 점 에 첨부 된 더 미 를 합병 할 때 우 리 는 합병 전의 두 더 미 를 보존 해 야 하기 때문에 지속 가능 한 사용 이 필요 하 다 는 것 이다.
뭐? 공간 이 얼마나 넓다 고?
잘 모 르 겠 어 요. 그래서 바늘 을 찔 렀 어 요.
사실 이 문 제 는 contest hunter 약 승 호 책 # round 1 의 T3 와 유사 하 다.
구체 적 으로 내 가 말 한 것 은 잘 모 르 겠 지만, 어쨌든 그림 을 잘 그리 면 코드 를 쓸 수 있다.
복잡 도 에 이르다.O(SPFA+mlogm+klogk)
또: 왜 나 는 늘 TM 자체 코드 가 길 어!못 참 겠 어!
할아버지 3 개 3 천 B 쌓 으 세 요. 제 가 특별히 2 개 쌓 으 세 요. 4000 + B!!
코드:

#include "queue"
#include "cstdio"
#include "cstring"
#include "iostream"
#include "algorithm"
#define N 10010
#define M 100010
using namespace std;
long long fa[N];
long long v[N];
long long dis[N];
long long head[N];
long long headf[N];
long long on[M];
long long n,m,k;
struct line
{
    long long from,to,val;
}f[M];
long long cnt,cntf;
struct node
{
    long long from,to,val,next;
}edge[M],edgef[M];
struct Heap
{
    Heap *lson,*rson;
    long long val,to,h;
    Heap()
    {
        lson=rson=0x0,val=to=0,h=-1;
    }
}*heap[N];
Heap *merge(Heap *x,Heap *y)
{
    if(!x)return y;
    if(!y)return x;
    if(x->val>y->val)swap(x,y);
    x->rson=merge(x->rson,y);
    long long lh=-1,rh=-1;
    if(x->lson)lh=x->lson->h;
    if(x->rson)rh=x->rson->h;
    if(rh>lh)swap(x->lson,x->rson);
    x->h=rh+1;
    return x;
}
Heap *Merge(Heap *x,Heap *y)
{
    if(!x)return y;
    if(!y)return x;
    if(x->val>y->val)swap(x,y);
    Heap *ret=new Heap();
    *ret=*x;
    ret->rson=Merge(ret->rson,y);
    long long lh=-1,rh=-1;
    if(ret->lson)lh=ret->lson->h;
    if(ret->rson)rh=ret->rson->h;
    if(rh>lh)swap(ret->lson,ret->rson);
    ret->h=rh+1;
    return ret;
}
void init()
{
    memset(head,-1,sizeof(head));
    memset(headf,-1,sizeof(headf));
    cnt=cntf=1;
}
void edgeadd(long long from,long long to,long long val)
{
    edge[cnt].from=from,edge[cnt].to=to,edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void fadd(long long from,long long to,long long val)
{
    edgef[cntf].from=from,edgef[cntf].to=to,edgef[cntf].next=headf[from];
    edgef[cntf].val=val;
    headf[from]=cntf++;
}
void spfa(long long s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(v,0,sizeof(v));
    queue<long long>q;
    q.push(s);
    v[s]=1;
    dis[s]=0;
    while(!q.empty())
    {
        long long u=q.front();
        q.pop();
        v[u]=0;
        for(long long i=head[u];i!=-1;i=edge[i].next)
        {
            long long to=edge[i].to;
            if(dis[u]+edge[i].val0;
                fa[to]=i;
                on[fa[to]]=1;
                if(!v[to])
                {
                    v[to]=1;
                    q.push(to);
                }
            }
        }
    }
}
void Chaos_solve()
{
    memset(v,0,sizeof(v));
    queue<long long>q;
    q.push(n);
    v[n]=1;
    while(!q.empty())
    {
        long long u=q.front();
        q.pop();
        for(long long i=headf[u];i!=-1;i=edgef[i].next)
        {
            long long to=edgef[i].to;
            if(on[i]==0)
            {
                Heap *tmp=new Heap();
                tmp->val=edgef[i].val,tmp->to=edgef[i].to;
                heap[u]=Merge(heap[u],tmp);
            }else
            {
                heap[u]=Merge(heap[u],heap[to]);
            }
        }
        for(long long i=head[u];i!=-1;i=edge[i].next)
        {
            long long to=edge[i].to;
            if(v[to])continue;
            if(on[i])
            {
                q.push(to);
                v[to]=1;
            }   
        }
    }
} 
struct ele
{
    long long val;
    Heap *HEAP; 
};
bool operator < (ele a,ele b)
{
    return a.val+a.HEAP->val > b.val+b.HEAP->val;
}
priority_queueqq;
int main()
{
    init();
    scanf("%lld%lld%lld",&n,&m,&k);
    for(long long i=1;i<=m;i++)
    {
        long long x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        edgeadd(y,x,z);
    }
    spfa(n);
    for(long long i=1;i<=m;i++)
    {
        f[i].from=edge[i].to;
        f[i].to=edge[i].from;
        f[i].val=dis[edge[i].from]-dis[edge[i].to]+edge[i].val;
        fadd(f[i].from,f[i].to,f[i].val);
        edge[i].val=f[i].val;
    }
    Chaos_solve();
    ele tmp;
    tmp.val=0,tmp.HEAP=heap[1];
    qq.push(tmp);
    long long ans=0;
    for(long long i=2;i<=k;i++)
    {
        if(qq.empty())break;
        ele u=qq.top();
        qq.pop();
        ans=u.val+u.HEAP->val;
        ele noname;
        noname.val=u.val;
        noname.HEAP=Merge(u.HEAP->lson,u.HEAP->rson);
        if(noname.HEAP)qq.push(noname);
        noname.val=ans;
        noname.HEAP=heap[u.HEAP->to];
        if(noname.HEAP)qq.push(noname);
    }
    printf("%lld
",ans+dis[1]);
}