낙곡3953 NOIP2017 공원구경 최단로도+토폴로지 순서+dp

제목 링크 제목: n개의 점 m변에 있는 벨트맵을 드리겠습니다. 1번에서 n번까지의 최단길은 디스입니다. k(k<=50)를 드리겠습니다. 모든 1에서 n까지의 경로의 길이가 디스+k의 수량을 초과하지 않도록 하세요.
문제: 분명히 우리는 최단로를 먼저 처리해야 한다. 앞으로 다시는 SPFA를 쓰지 않을 것이다. NOI 2018은 SPFA가 끊겼고 많은 사람들이 SPFA의 복잡도가 틀렸다고 말하기 때문에 디제이를 할 수밖에 없다.최단로를 처리한 후 k=0이면 최단로 계수입니다.계수를 하려면, 우리는 그림에서 dp를 생각해야 한다고 어렵지 않다.우리는 하나의 변권이 모두 0인 고리만 있다면, 우리의 문제를 만족시키는 경로는 무수히 많을 것이다. 왜냐하면 고리 안에서 임의로 여러 바퀴를 돌고 나올 수 있기 때문이다.그렇다면 우리가 무궁무진한 다해가 있는지 아닌지를 판단하는 것은 모두 0의 고리가 있는지 없는지를 찾는 것이다.우리는 먼저 최단로도를 처리할 수 있다. 최단로도의 의미는 모든dis[x]+dis[x][y]=dis[y]의 변이 연결된 그림이다. 하나의 성질은 변권이 정수라면 최단로도는DAG이다.DAG는 토폴로지 서열을 정할 수 있다. 만약에 마지막에 모든 점의 입도가 0이면 모두 0의 고리가 존재하지 않는다. 그렇지 않으면 모두 0의 고리가 있다. 만약에 값이 0의 가장자리가 반드시 두 점 사이의 최단거리 가장자리를 길게 하지 않기 때문에 반드시 최단거리 트리에 있고 고리를 형성하면 그 중 어느 한 점의 입도가 0이 될 수 없기 때문에 토폴로지 서열의 입도를 판단하면 된다.그림 토폴로지 정렬 후 그림의 토폴로지 순서에 따라DAG에서 dp도 고전적인 방법인데 여기서 우리는 이 방식을 채택할 것이다.k가 작기 때문에 우리의 dp 상태에 나타날 가능성이 높다. 현재 점은 반드시 dp값과 관련이 있기 때문에 우리는 dp[i][j] dp[i][i][i] [j]를 설정하여 dis[i]보다 큰 j의 경로수를 나타낼 수 있다. 그러면 경로 x-4>yx-3>>y, dp[x][j] [j] dp[x] [j][j]]는 dp[y][y][y] [j] [j]][y] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j]]]]][y] [j] [j] [j] [y] [y] [j] [s] [s] [[s] [y] [s] [s] [s] [y] [sis[x]]이(가) 기여했습니다.그러면 우리의 방법은 j를 매거한 다음에 토폴로지 순서에 따라 x를 매거하고 x에서 출발한 모든 변을 매거하여 dp를 진행하는 것이다.외층은 j를 매거하는 것을 주의해야 한다. dp 과정에서 외층이 x를 매거하면DAG에 고리가 없지만 이곳의 가장자리는 원도를 매거하는 가장자리이기 때문에 나중에 고리가 x로 돌아갈 수 있다. 답을 얻는 것은 잘못된 것이다.그리고 이 dp는 매거된 층수가 많은 것처럼 보이지만 사실 복잡도가 높지 않다. 모든 변이 한 번만 매거되고 모든 점은 k+1(0~k)회만 매거되기 때문에 전체적인 복잡도는 O(n∗k)O(n𕓭k)이다.마지막으로 말하자면 이 문제는 NOIP에서 카드 상수였다. 무수한 신번들이 모두 끊겼다. 나는 내가 로곡에서 운행하는 속도를 보았는데 NOIP 측정기에 놓아도 틀림없이 시간을 초과할 것이다.코드:

#include 
using namespace std;

int T,n,m,k,p,hed[100010],cnt,dis[100010],vis[100010];
struct node
{
    int from,to,dis,next;
}a[200010],e[200010];
int dp[1000010][51],hed2[100010],cnt2,ru[100010],xu[100010],shu;
priority_queueint,int> > q;
int que[100010],h,t,pd;
long long ans;
void add(int from,int to,int dis)
{
    a[++cnt].to=to;
    a[cnt].from=from;
    a[cnt].dis=dis;
    a[cnt].next=hed[from];
    hed[from]=cnt;
}
void add2(int from,int to,int dis)
{
    e[++cnt2].to=to;
    e[cnt2].dis=dis;
    e[cnt2].next=hed2[from];
    hed2[from]=cnt2;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&k,&p);
        memset(hed,0,sizeof(hed));
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=cnt;++i)
        {
            a[i].to=0;
            a[i].dis=0;
            a[i].next=0;
        }
        cnt=0;
        for(int i=1;i<=m;++i)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        dis[1]=0;
        q.push(make_pair(0,1));
        while(!q.empty())
        {
            int x=q.top().second;
            q.pop();
            if(vis[x])
            continue;
            vis[x]=1;
            for(int i=hed[x];i;i=a[i].next)
            {
                int y=a[i].to;
                if(dis[y]>dis[x]+a[i].dis)
                {
                    dis[y]=dis[x]+a[i].dis;
                    q.push(make_pair(-dis[y],y));
                }
            }
        }
        memset(hed2,0,sizeof(hed2));
        memset(ru,0,sizeof(ru));
        for(int i=1;i<=cnt2;++i)
        {
            e[i].to=0;
            e[i].dis=0;
            e[i].next=0;
        }
        for(int i=1;i<=cnt;++i)
        {
            if(dis[a[i].from]+a[i].dis==dis[a[i].to])           
            {
                add2(a[i].from,a[i].to,a[i].dis);
                ++ru[a[i].to];
            }
        }
        h=1;
        t=0;
        shu=0;
        memset(xu,0,sizeof(xu));
        for(int i=1;i<=n;++i)
        {
            if(!ru[i])
            que[++t]=i; 
        }
        while(h<=t)
        {
            int x=que[h];
            xu[++shu]=x;
            for(int i=hed2[x];i;i=e[i].next)
            {
                int y=e[i].to;
                --ru[y];
                if(!ru[y])
                que[++t]=y;
            }
            ++h;
        }
        pd=0;
        for(int i=1;i<=n;++i)
        {
            if(ru[i])
            {
                pd=1;
                break;
            }
        }
        if(pd==1)
        {
            printf("-1
");
            continue;
        }
        memset(dp,0,sizeof(dp));
        dp[1][0]=1;
        for(int j=0;j<=k;++j)
        {
            for(int i=1;i<=n;++i)
            {
                int x=xu[i];
                for(int l=hed[x];l;l=a[l].next)
                {
                    int y=a[l].to;
                    if(j+a[l].dis-(dis[y]-dis[x])<=k)
                    dp[y][j+a[l].dis-(dis[y]-dis[x])]=(dp[y][j+a[l].dis-(dis[y]-dis[x])]+dp[x][j])%p;
                }
            }
        }
        ans=0;
        for(int i=0;i<=k;++i)
        ans=(ans+dp[n][i])%p;
        printf("%lld
",ans);
    }
    return 0;
}

PS: 반년 만에 NOIP 문제를 풀다니 정말 발전이 없네요.이것은 나의 NOIP에서 유일하게 즉석에서 0이 된 문제였지만, 지금 다른 사람이 말하는 것을 들은 후에도 몇 번을 내고서야 통과했다. 비록 틀린 것은 모두 작은 부분이지만, 내가 그렇게 많이 진보한 것 같지 않다는 것을 알아차렸다.