HDU-4849 Wow! Such City!,最短路！

Wow! Such City!

   题意：题面很难理解，幸亏给出了提示，敲了一发板子过了。给出x数组y数组和z数组的求法，并给出x、y的前几项，然后直接利用所给条件构造出z数组再构造出C数组即可，Cij表示i点到j点的路长，然后再跑个dij就可以求出0点到其他点的最短路，然后将这些最短路对M取余求所有取余值的最小值。需要注意的是Cij=Z(i*n+j)，也就是X、Y、Z数组都要开到(n-1)*n+n。理解了其实也就是水题了，题意这样东扯西扯真是迷。。

const int N=1e6+1000;

ll w[1001][1001],d[1001];

ll z[N],x[N],y[N];

int v[N],vis[N];

int n,m;

void init()

{

    int fuck=(n-1)*n+n;

    for(int i=2; i<fuck; i++)

    {

        x[i]=(12345+x[i-1]*23456+x[i-2]*34567+x[i-1]*x[i-2]*45678)%5837501;

        y[i]=(56789 +y[i-1]*67890 +y[i-2]*78901+y[i-1]*y[i-2]*89012)%9860381;

    }

    for(int i=0;i<fuck;i++)  z[i]=(x[i]*90123+y[i])%8475871+1;

    for(int i=0; i<n; i++)

        for(int j=0; j<n; j++)

            w[i][j]=i==j?0:z[i*n+j];

//    for(int i=0; i<fuck ; i++)

//        printf("%8d",i);

//    puts("");

//    for(int i=0; i<fuck ; i++)

//        printf("%8I64d",x[i]);

//    puts("");

//    for(int i=0; i<fuck ; i++)

//        printf("%8I64d",y[i]);

//    puts("");

//    for(int i=0; i<fuck ; i++)

//        printf("%8I64d",z[i]);

//    puts("\n");

//    for(int i=0; i<n; i++)

//    {

//        for(int j=0; j<n; j++)

//            printf("%8I64d",w[i][j]);

//        puts("");

//    }

//    puts("");

}

void dij()

{

    memset(v,0,sizeof(v));

    memset(vis,0,sizeof(vis));

    int ans=INF;

    for(int i=0; i<n; i++) d[i]=i==0?0:INF;

    for(int i=0; i<n; i++)

    {

        int x,mm=INF;

        for(int j=0; j<n; j++)

            if(!vis[j]&&mm>=d[j])

                mm=d[x=j];

        vis[x]=1;

        for(int j=0; j<n; j++)

            d[j]=min(d[j],d[x]+w[x][j]);

    }

//    puts("");

//    for(int i=1; i<n; i++)

//    {

//        printf("%8I64d",d[i]);

//        int tmp=d[i]%m;

//        v[tmp]++;

//    }

//    puts("");

    for(int i=1; i<n; i++)

    {

        int tmp=d[i]%m;

        ans=min(ans,tmp);

    }

    printf("%d\n",ans);

}

int main()

{

    while(~scanf("%d%d%I64d%I64d%I64d%I64d",&n,&m,&x[0],&x[1],&y[0],&y[1]))

    {

        init();//生成Z数组，W数组

        dij();

    }

    return 0;

}