http://acm.hdu.edu.cn/showproblem.php?pid=4849

会有非常多奇怪的Wa的题。当初在西安就不知道为什么wa，昨晚做了，由于一些Sb错误也wa了非常久。这会儿怎么写都会AC。

。。。

收获：

1、还是基本都构思好在去写程序，由于当时没过。昨晚心里有阴影。敲得非常慢，并且最開始各种取模以防止漏掉，太保守了......以后一定先估算是不是须要取模防止TLE，当然时间够的话还是适当多取个模防止莫名其妙的错误、、

2、假设出错，注意參数是不是对的，最開始写好之后。由于m和n写混。例子卡了，，最后换了还有一个版本号的最短路，还是由于一个变量写混了，WA了非常久

3、以后比赛期间假设时间还有并且不知为什么没过。考虑自己又一次写吧，给别人看代码排错还是不太easy搞出来的。

4、数据大的时候 开数组果断都long long吧

5、最重要的----假设RE 。先看数组有没有开错--我最開始由于键盘按键错位。，少敲了个0。一直RE，其次，也是很重要的，初始化。不要太懒直接memset。我

up=MAXN*MAXN，然后TLE了非常久，，，以及时间跑的非常长。，。

843MS AC

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

#define ll long long

#define INF 0x03F3F3F3F

const int N = 1234567+10;

const int MAXN=1000+30;

const int MOD1=5837501;

const int MOD2=9860381;

const int MOD3=8475871;

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

ll c[1010][1010];

ll lowcost[MAXN];

int vis[MAXN];

int n,m;

void calC()

{

    int up=n*n;

    for(int k=0;k<2;k++)

        z[k]=( x[k]*90123  + y[k] ) % MOD3 +1;

    for(int k=2;k<up;k++)

    {

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

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

         z[k]=( x[k]*90123  + y[k] ) % MOD3 +1;

    }

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

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

        {

            if(i == j){c[i][j]=0;continue;}

            c[i][j]=z[i*n+j];

        }

}

void Dij()

{

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

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

        lowcost[i]=INF;

    vis[0]=1;

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

        lowcost[i]=c[0][i];

    lowcost[0]=0;

    int pre=0,mmin=INF;

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

    {

        mmin=INF;

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

            if(vis[j] == 0 && lowcost[pre]+c[pre][j]<lowcost[j])

            {

                lowcost[j]=lowcost[pre]+c[pre][j];

            }

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

        {

            if(vis[j] == 0 && lowcost[j]<mmin)

            {

                mmin=lowcost[j];

                pre=j;

            }

        }

        vis[pre]=1;

    }

}

int solve()

{

    int mmin=INF,tmp;

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

    {

        tmp=lowcost[i]%m;

        if( tmp< mmin  )

            mmin=tmp;

    }

    return mmin;

}

int main()

{

    //freopen("hdu4849.txt","r",stdin);

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

    {

        calC();

        Dij();

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

    }

    return 0;

}

再贴还有一个版本号1515MS AC

-----可见人家吉大的模板还是效率非常高的，吉大的仅仅花了一半时间。，。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

#define ll __int64

const ll INF = 0x03F3F3F3F;

//const ll INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1010*1010+1000;

const int MAXN=1000+30;

const int MOD1=5837501;

const int MOD2=9860381;

const int MOD3=8475871;

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

ll c[1010][1010];

ll lowcost[MAXN];

int vis[MAXN];

int n,m;

void calC()

{

   // x[0]%=5837501,x[1]%=5837501;

  //  y[0]%=9860381,y[1]%=9860381;

    int up=(n)*(n);/////////

    for(int k=0;k<2;k++)

        z[k]=(( x[k]*90123 ) %MOD3 + y[k] ) % MOD3 +1;

    for(int k=2;k<up;k++)

    {

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

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

        z[k]=(( x[k]*90123 ) %MOD3 + y[k] ) % MOD3 +1;

    }

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

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

        {

            if(i == j)c[i][j]=0;

            else

            c[i][j]=z[i*n+j];

        }

}

void Dij()

{

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

        lowcost[i]=INF;

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

    {

        lowcost[i]=c[0][i];

        vis[i]=0;

    }

    lowcost[0]=0;vis[0]=1;

    int u=0;

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

    //while(1)

    {

        int mmin=INF;

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

            if(!vis[j] && lowcost[j]<mmin)

        {

            u=j;

            mmin=lowcost[j];

        }

       // if(mmin == INF)break;

        vis[u]=1;

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

        {

            if(!vis[k] && lowcost[u]+c[u][k]<lowcost[k])

                lowcost[k]=lowcost[u]+c[u][k];

        }

    }

}

int solve()

{

    int mmin=INF,tmp;

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

    {

        tmp=lowcost[i]%m;

        if( tmp< mmin )

            mmin=tmp;

    }

        //mmin=min(mmin,lowcost[i]%m);

    return mmin;

}

int main()

{

    //freopen("hdu4849.txt","r",stdin);

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

    {

        calC();

        Dij();

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

    }

    return 0;

}