NOI 2018: 돌아 오 는 길

제목 대의: 문제 면 \ (\; \; \; \; \; \; \; \; \; \; \; \) 은 방향 없 는 그림 을 정 하고 각 변 에 길이 와 높이 가 있 으 며, 특정한 점 pi 에서 1 번 점 까지 의 최 단 로 를 여러 번 물 어보 고, 매개 변수 qi 를 제시 하여 pi 에서 출발 하여 높이 > qi 의 변 으로 만 도착 할 수 있 는 모든 점 을 대가 없 이 도착 할 수 있 도록 규정 한다.
구체 적 인 사고: \ (\; \;; \) 크 루스 칼 재 구성 트 리재 구성 트 리 에 노드 하 나 를 새로 만 들 고 두 개의 연결 블록 을 새로운 점 의 아들 로 생각 합 니 다.
SPFA 가 끊 겼 다 니, 정말 통쾌 하 다. dij 얼마나 좋 은 데 AC 코드

#include
#include
#include
#include
#include
using namespace std;

int n,m,T,q,x,y,z,zz,k,s,v0,p0,lastans,v,p,nowans;
const int N=1000000,INF=1e9;
int dis[N],vis[N],f[N],fa[N],ans[N],out[N],FA[N][20],H[N];
vector son[N];
struct link
{
    int top,fi[N],ne[N],la[N],to[N],l[N],h[N];
    inline void clear()
    {
        top=0,memset(fi,0,sizeof fi),memset(ne,0,sizeof ne),memset(la,0,sizeof la),memset(to,0,sizeof to),memset(l,0,sizeof l),memset(h,0,sizeof h);
    }
    inline void add(int x,int y,int z,int H)
    {
        top++,to[top]=y,l[top]=z,h[top]=H;
        if(fi[x]==0)fi[x]=top;else ne[la[x]]=top;
        la[x]=top;
    }
}L;
struct node
{
    int id,dis;
    bool operator < (const node &a) const {return a.dis < dis;}
};
priority_queue que;
inline void DIJKSTRA()
{
    for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0;
    dis[1]=0;while(!que.empty())que.pop();
    node tmp;
    tmp.id=1;tmp.dis=0;que.push(tmp);
    while (!que.empty()) 
    {
        int now=que.top().id;
        que.pop();
        if (vis[now]) continue;
        vis[now]=true;
        for (int i=L.fi[now];i;i=L.ne[i]) 
        {
            if (!vis[L.to[i]]&&dis[L.to[i]]>dis[now]+L.l[i]) 
            {
                dis[L.to[i]]=dis[now]+L.l[i];
                tmp.id=L.to[i];tmp.dis=dis[L.to[i]];
                que.push(tmp);
            }
        }
    }
}
struct E{int x,y,l,h;}e[N];
inline bool cmp(E a,E b){return a.h>b.h;}
inline int ASK(int x){if(fa[x]==x)return x;else return fa[x]=ASK(fa[x]);}
void dfs(int x)
{
    for(int i=1;i<=19;i++)FA[x][i]=FA[FA[x][i-1]][i-1];
    for(int i=0;i=0;i--)if(H[FA[now][i]]>p)now=FA[now][i];
            lastans=ans[now];
            printf("%d
",lastans);
        }
    }
    return 0;
}

다음으로 전송:https://www.cnblogs.com/Orange-User/p/9362738.html