学步园

题目大意：给定一个无向图，求源点到汇点的最短路，其中有k次机会把边权变为0

非常水的分层图。。话说所谓分层图其实就是多一维的SPFA。。。还起了这么个高大上的名字

这题裸SPFA过不去 要加堆优化 我的堆优化一定是写的有毛病 把heap[top--]=heap[0]改成top--就死活过不去 把魔法森林改一下测试了一下结果居然WA了

总之贴代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 10100
using namespace std;
struct abcd{
    int to,f,next;
}table[100100];
typedef pair<int,int> ABCD;
ABCD heap[M*10];
unsigned short r,h;
int head[M],tot,top;
int n,m,k,s,t,ans=0x3f3f3f3f;
int f[M][11],pos[M][11];
void push_up(int t)
{
    while( t>1 && f[heap[t].first][heap[t].second]<f[heap[t>>1].first][heap[t>>1].second] )
        swap(heap[t],heap[t>>1]),swap(pos[heap[t].first][heap[t].second],pos[heap[t>>1].first][heap[t>>1].second]),t>>=1;
}
void insert(ABCD x)
{
    heap[++top]=x;
    pos[x.first][x.second]=top;
    push_up(top);
}
void pop()
{
    pos[heap[1].first][heap[1].second]=0;
    heap[1]=heap[top];
    //top--;
    heap[top--]=heap[0];
    pos[heap[1].first][heap[1].second]=1;
    int t=2;
    while(t<=top)
    {
        if( f[heap[t].first][heap[t].second]>f[heap[t+1].first][heap[t+1].second] && t<top )
            t++;
        if( f[heap[t].first][heap[t].second]<f[heap[t>>1].first][heap[t>>1].second] )
            swap(heap[t],heap[t>>1]),swap(pos[heap[t].first][heap[t].second],pos[heap[t>>1].first][heap[t>>1].second]),t<<=1;
        else
            break;
    }
}
void SPFA()
{
    int i;
    ABCD x;
    memset(f,0x3f,sizeof f);
    insert( make_pair(s,0) );
    f[s][0]=0;
    while(top)
    {
        x=heap[1];pop();
        for(i=head[x.first];i;i=table[i].next)
        {
            if( f[x.first][x.second]+table[i].f<f[table[i].to][x.second] )
            {
                f[table[i].to][x.second]=f[x.first][x.second]+table[i].f;
                if(!pos[table[i].to][x.second])
                    insert( make_pair(table[i].to,x.second) );
                else
                    push_up( pos[table[i].to][x.second] );
            }
            if( x.second<k && f[x.first][x.second]<f[table[i].to][x.second+1] )
            {
                f[table[i].to][x.second+1]=f[x.first][x.second];
                if(!pos[table[i].to][x.second+1])
                    insert( make_pair(table[i].to,x.second+1) );
                else
                    push_up( pos[table[i].to][x.second+1] );
            }
        }
    }
    for(i=0;i<=k;i++)
        ans=min(ans,f[t][i]);
}
void add(int x,int y,int z)
{
    table[++tot].to=y;
    table[tot].f=z;
    table[tot].next=head[x];
    head[x]=tot;
}
int main()
{
    int i,x,y,z;
    cin>>n>>m>>k>>s>>t;s++;t++;
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&x,&y,&z),x++,y++,add(x,y,z),add(y,x,z);
    SPFA();
    cout<<ans<<endl;
}