[NOIP2017] 공원 구경.

제목: dis(1,n) <=Mindis(1,n) + K d i s(1,n) < = M i n D i s(1,n) + K 경로 수

알고리즘 1: DP

일단 Day1 D a y 1의 DP D P 가 어디 갔는지 생각해 보실 수 있을 것 같아요.
맞아요. K≤50K≤50만 더 주의하면 Kk와 관련된 DP D P라고 생각할 수 있을 거예요.

①: 30pts:K=0 고려 30p t s:K=0

우회전LuoguP1608 경로 통계(P1144 최단거리 계수는 A를 따라 떨어질 수 있음)

②: 70pts 고려 70p t s: 0 0 변이 없다

dis1u d i s 1 u를 설정하면 1부터 u까지의 최단길을 표시하고, disnu d i s n u를 설정하면 u에서 n까지의 최단길을 표시한다(이것은 역도를 만들어 뛰어나올 수 있다)
f[u][j]f[u][j]를 고려하면dis(1,u)≤dis1u+jdis(1,u)≤dis1u+j의 경로수
그러면 edge(u, v, w) e d g e(u, v, w)
그렇다면 1 -3>u -3>v 1 -3>u -3>v 이 경로의 길이는 dis1u+j+w - dis1v d i s 1 u + j + w - dis1v i s 1 v
dis1u+w -3 dis1v+j≤K d i s 1 u + w -3 d i s 1 v + j≤ K
f[u][j]f[u][j]에서 f[v][dis1u+j+w - dis1v] f [v] [d i s 1 u + j + w - d i s 1 v]
그래서 그냥 1, 1로 쭉 가다가 O(KM) DP O (KM) D P 하면 ok o k.
물론 그래도 문제가 있어요.
왜냐면 저희가 dis1 d i s 1의 작은 점을 업데이트해야 되기 때문에.
그래서 dis1 d i s 1열에 따라 이동하면 70pts 70p t s가 됩니다.

③: 100pts: 100p t s 고려:

0 0 변이 있는 그림은 디스1 d i s 1에 따라 정렬하면 안 되는 것이 분명하다
예를 들어 a-3>b -3>c, w=0 a-3>b -3>c, w=0
그의 방향도 때문에 업데이트 순서는 분명히 a, b, c a, b, c
그래서 토폴로지 정렬을 고려하여 0 0 변의 두 단점의 업데이트 순서를 정합니다
즉, 0 0 변에 새 그림을 추가한 다음에 새 그림 토폴로지 정렬에 대해 0 0 0 점의 업데이트 순서를 정합니다
그리고 -3-1 -3-1의 경우 조건을 만족시키는 경로에 0 0환이 있는 것이 분명하다
토폴로지 정렬이 끝났고 입도가 0 0이 아니라는 것은 이 점이 0 0 링에 있다는 것을 설명한다
같은 0 0 링의 임의의 점에서 1 1까지의 최단길과 n n까지의 최단길은 모두 같다
그래서 이 점 ii가 dis1i+disni<=dis1n+K d i s 1 i + d i s n i <=d i s 1 n + K 를 충족하면 -3-1 을 출력할 수 있습니다
그리고 마지막으로 dis1 d i s 1 또는 disn d i s n을 첫 번째 키워드로 하고, 토폴로지 서열을 두 번째 키워드로 정렬한 다음 이동하면 ok o k
여기는 시험장 코드... 최단길은 라인 트리로 달리는 거예요.

#include
#include
#include
#include
#define re register int
#define fp(i,a,b) for(re i=a,I=b;i<=I;++i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sdf(T&x){
    char c;T y=1;while(c=gc(),(c<48||571)if(c=='-')y=-1;x=c^48;
    while(c=gc(),4758)x=(x<<1)+(x<<3)+(c^48);x*=y;
}
using namespace std;
const int N=1e5+5,M=2e5+5;
typedef int arr[N];
struct eg{int nx,to,w;}e[M<<1],E[M];
int T,n,m,K,P,ce=1,Ce,ans,*dis,f[N][55];arr dis1,disn,fi1,fin,vis,in,q,Fi,id,da;
namespace seg{
    int tr[N<<2],sgt;
    inline void Set(re n){sgt=1;while(sgt<=n)sgt<<=1;--sgt;tr[0]=N-1;}
    inline void clr(){fp(i,1,(sgt<<1)+1)tr[i]=0;}
    inline int cmp(const re&a,const re&b){return dis[a]inline void mdy(re x,re w){for(re i=x+sgt;dis[tr[i]]>w;i>>=1)tr[i]=x;dis[x]=w;}
    inline void del(re x){tr[x+=sgt]=0;x>>=1;while(x)tr[x]=cmp(tr[x<<1],tr[x<<1|1]),x>>=1;}
}
using namespace seg;
void dij(re s,re*Dis,re*fi){
    dis=Dis;memset(dis,9,4*(n+1));clr();mdy(s,0);
    fp(T,1,n){
        re u=tr[1];del(u);
        for(re i=fi[u],v;i;i=e[i].nx)
            if(dis[v=e[i].to]>dis[u]+e[i].w)
                mdy(v,dis[u]+e[i].w);
    }
}
inline void add(re u,re v,re w,re*fi){e[++ce]=(eg){fi[u],v,w};fi[u]=ce;}
inline void ADD(re u,re v){E[++Ce]=(eg){Fi[u],v,0};Fi[u]=Ce;}
inline bool comp(const re&a,const re&b){return dis1[a]==dis1[b]?id[a]bool topsort(){
    re h=1,t=0;
    fp(i,1,n)if(!in[i])q[++t]=i;
    while(h<=t){
        re u=q[h++];
        for(re i=Fi[u],v;i;i=E[i].nx)
            if(!--in[v=E[i].to])q[++t]=v;
    }
    fp(i,1,n)id[q[i]]=i;
    fp(i,1,n)if(in[i]&&dis1[i]+disn[i]<=K+dis1[n])return 1;
    return 0;
}
inline void mod(re&a){a>=P?a-=P:0;}
int main(){
    #ifndef ONLINE_JUDGE
        file("park");
    #endif
    sdf(T);
    while(T--){
        memset(fi1,0,sizeof fi1);memset(fin,0,sizeof fin);
        memset(Fi,0,sizeof Fi);ce=Ce=ans=0;
        sdf(n);sdf(m);sdf(K);sdf(P);re u,v,w;Set(n);
        while(m--){
            sdf(u),sdf(v),sdf(w),add(u,v,w,fi1),add(v,u,w,fin);
            if(!w)ADD(u,v),++in[v];
        }
        dij(1,dis1,fi1);dij(n,disn,fin);;
        if(topsort()){puts("-1");continue;}
        memset(f,0,sizeof f);f[1][0]=1;
        fp(i,1,n)da[i]=i;sort(da+1,da+n+1,comp);
        fp(k,0,K)fp(p,1,n)
            for(re u=da[p],d=dis1[u],i=fi1[u];i;i=e[i].nx)
                if(e[i].w-dis1[e[i].to]+d+k<=K)
                    mod(f[e[i].to][e[i].w-dis1[e[i].to]+d+k]+=f[u][k]);
        fp(k,0,K)mod(ans+=f[n][k]);
        printf("%d
",ans);
    }
return 0;
}

위의 이 방법은 상수가 아직 적지 않은데, 사실 생각해 보면 알 수 있을 뿐만 아니라, 쓰기도 매우 길다
그리고 더 아름다운 방법이 있어요. 바로 기억화 검색이에요.

알고리즘2: 기억화 검색

한 번만 반대로 가는 최단길.
f[u][k] f[u] [k]는 디스(u, n) <=Mindis(u, n) + k d i s(u, n) < = M i n D i s(u, n) + k의 시나리오 수를 의미하며, 정답은 f[1] [K] f [1] [K]
egde(u, v, w) e g d e(u, v, w) 고려
같은 이치로 이 쪽으로 가면 디스(v, n) = Mindis(v, n) + w - Mindis(u, n) d i s(v, n) = M i n D i s(v, n) + w - - - - - - M i n D i s(u, n)
⇒f[u][k]=∑f[v][k−(MinDis(v,n)−MinDis(u,n)+w)] ⇒ f [ u ] [ k ] = ∑ f [ v ] [ k − ( M i n D i s ( v , n ) − M i n D i s ( u , n ) + w ) ]
이렇게 해서 0 0 라운드 어떻게 해요?검색할 때 instack i n s t a c k만 기록하면 ok ok.
현재 v v가 검색된 창고에 있으면 바로 1 - 1 - 1 으로 되돌아갈 수 있습니다

#include
#include
#define re register int
#define fp(i,a,b) for(re i=a,I=b;i<=I;++i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sdf(T&x){
    char c;T y=1;while(c=gc(),(c<48||571)if(c=='-')y=-1;x=c^48;
    while(c=gc(),4758)x=(x<<1)+(x<<3)+(c^48);x*=y;
}
const int N=1e5+5,M=2e5+5;
typedef int arr[N];
struct eg{int nx,to,w;}e[M<<1];
int T,n,m,K,P,ce,f[N][51];arr dis,f1,fn;bool in[N][51];
namespace seg{
    int tr[N<<2],sgt;
    inline void Set(re n){sgt=1;while(sgt<=n)sgt<<=1;--sgt;tr[0]=N-1;}
    inline void clr(){fp(i,1,(sgt<<1)+1)tr[i]=0;}
    inline int cmp(const re&a,const re&b){return dis[a]inline void mdy(re x,re w){for(re i=x+sgt;dis[tr[i]]>w;i>>=1)tr[i]=x;dis[x]=w;}
    inline void del(re x){tr[x+=sgt]=0;x>>=1;while(x)tr[x]=cmp(tr[x<<1],tr[x<<1|1]),x>>=1;}
}
using namespace seg;
void dij(){
    memset(dis,9,4*(n+1));clr();mdy(n,0);
    fp(T,1,n){
        re u=tr[1];del(u);
        for(re i=fn[u],v;i;i=e[i].nx)
            if(dis[v=e[i].to]>dis[u]+e[i].w)
                mdy(v,dis[u]+e[i].w);
    }
}
inline void add(re u,re v,re w,re*fi){e[++ce]=(eg){fi[u],v,w};fi[u]=ce;}
inline void mod(re&a){a>=P?a-=P:0;}
int dfs(re u,re k){
    if(in[u][k])return -1;
    if(f[u][k])return f[u][k];
    in[u][k]=1;u==n?f[u][k]=1:0;
    for(re i=f1[u],v,w,tp;i;i=e[i].nx)
        if((tp=dis[v=e[i].to]-dis[u]+e[i].w)<=k){
            if((w=dfs(v,k-tp))==-1)return f[u][k]=-1;
            mod(f[u][k]+=w);
        }
    return in[u][k]=0,f[u][k];
}
int main(){
    #ifndef ONLINE_JUDGE
        file("park");
    #endif
    sdf(T);
    while(T--){
        memset(f,0,sizeof f);memset(in,0,sizeof in);
        sdf(n);sdf(m);sdf(K);sdf(P);Set(n);re u,v,w;
        memset(f1,ce=0,4*(n+1));memset(fn,0,4*(n+1));
        while(m--)sdf(u),sdf(v),sdf(w),add(u,v,w,f1),add(v,u,w,fn);
        dij();printf("%d
",dfs(1,K));
    }
return 0;
}