Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
InputThere are several test cases. Please process till EOF.
For each test case, there is only one line containing 6 integers
N,M,X0,X1,Y0,Y1.See the description
for more details. OutputFor each test case, output a single line containing a
single integer: the number of minimal category. Sample Input3 10 1 2 3 44 20 2 3 4 5 Sample Output110 Hint:
怎么说吧,就是一个又臭又长又水的单源最短路径外加算算MOD的题。
#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 1003
#define MAXK 1000*1000+1000
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m;
ll x[MAXK],y[MAXK],z[MAXK],c[MAXN][MAXN];
int cate[+];
void calc()
{
int max_k=(n-)*n+(n-);
for(int k=;k<=max_k;k++)
{
if(k>=)
{
x[k]=( + (x[k-] * ) % + (x[k-] * ) % + (x[k-] * x[k-] * ) % ) % ;
y[k]=( + (y[k-] * ) % + (y[k-] * ) % + (y[k-] * y[k-] * ) % ) % ;
}
z[k]=(x[k] * + y[k] ) % + ;
}
//for(int k=0;k<=max_k;k++) printf("x[%d]=%lld \t y[%d]=%lld \t z[%d]=%lld \n",k,x[k],k,y[k],k,z[k]);
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
if(i==j) c[i][j]=;
else c[i][j]=z[(i*n+j)];
//printf("%lld\t",c[i][j]);
}
//printf("\n");
}
}
bool vis[MAXN];
ll d[MAXN];
void spfa()
{
for(int i=;i<n;i++){
vis[i]=;
d[i]=INF;
}
vis[]=;
d[]=;
queue<int> q;
q.push();
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=;
for(int v=;v<n;v++)
{
if(u==v) continue;
ll tmp=d[v];
if(d[v]>d[u]+c[u][v]) d[v]=d[u]+c[u][v];
if(d[v]<tmp && !vis[v]) q.push(v),vis[v]=;
}
}
}
int main()
{
while(scanf("%d %d %lld %lld %lld %lld",&n,&m,&x[],&x[],&y[],&y[])!=EOF)
{
calc();
spfa();
memset(cate,,sizeof(cate));
for(int i=;i<n;i++)
{
//printf("d[%d]=%lld\n",i,d[i]);
cate[(d[i]%m)]++;
}
for(int i=;i<m;i++)
{
if(cate[i]!=)
{
printf("%d\n",i);
break;
}
}
}
}