P4768 [NOI2018] 归程

注意点 ：重构树相连起来 只是保证存在一条路径 但是树上的路径不能保证最短

既然下车步行了 就不用再考虑海拔高度了 尽量走最少的路就行了

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long lt;

lt read()
{
    lt f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}


const int maxn=800010;
int n,m,cnt;
lt Q,K,S;

struct node{int u, v;lt hi;}edge[maxn<<1];
bool cmp(node a,node b){return a.hi>b.hi;}

struct node2{int v,nxt;lt dis;}E[maxn<<1];
int head[maxn],tot;

lt d[maxn],vis[maxn],ff[maxn];
priority_queue< pair > q;

lt mi[maxn],val[maxn];
int gra[maxn][23];

void add(int u,int v,lt dis)
{
    E[++tot].nxt=head[u];
    E[tot].v=v; E[tot].dis=dis;
    head[u]=tot;
}

void dij()
{
    memset(vis,0,sizeof(vis));
    memset(d,111,sizeof(d)); d[1]=0;
    q.push(make_pair(0,1));

    while(!q.empty())
    {
        int u=q.top().second; q.pop();
        if(vis[u]) continue;

        vis[u]=1;
        for(int i=head[u];i;i=E[i].nxt)
        {
            int v=E[i].v;
            if(d[u]+E[i].dis=0;--j)//找到深度最小且海拔大于水位的节点
            if(gra[vi][j]&&val[gra[vi][j]]>pi) 
            vi=gra[vi][j];
            
            printf("%lld\n",last=mi[vi]);
        }
    }
    return 0;
}