题意： 让你求0到所有点最短路中对m取余最小的那个数。 思路： 简单题，直接根据题目给的公式把z求出来，然后建边，然后最短路，然后枚举每一个点对m取余记录最小，然后输出答案
题意：
让你求0到所有点最短路中对m取余最小的那个数。
思路：
简单题，直接根据题目给的公式把z求出来，然后建边，然后最短路，然后枚举每一个点对m取余记录最小，然后输出答案，然后ac.
#include<queue>
#define N_node 1111
#define N_edge 1111111
#define INF 1000000000
using namespace std;
typedef struct
{
int to ,next;
__int64 cost;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
__int64 s_x[N_node];
__int64 Z[N_edge];
void add(int a ,int b ,__int64 c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
}
void spfa(int s ,int n)
{
int mark[N_node] = {0};
for(int i = 0 ;i <= n ;i ++)
s_x[i] = INF;
mark[s] = 1 ,s_x[s] = 0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int xin ,tou;
tou = q.front();
q.pop();
mark[tou] = 0;
for(int k = list[tou] ;k ;k = E[k].next)
{
xin = E[k].to;
if(s_x[xin] > s_x[tou] + E[k].cost)
{
s_x[xin] = s_x[tou] + E[k].cost;
if(!mark[xin])
{
mark[xin] = 1;
q.push(xin);
}
}
}
}
return ;
}
int main ()
{
int n ,i ,j;
__int64 x1 ,x2 ,y1 ,y2 ,x ,y ,m;
while(~scanf("%d %I64d %I64d %I64d %I64d %I64d" ,&n ,&m ,&x1 ,&x2 ,&y1 ,&y2))
{
Z[1] = (x1 * 90123 + y1) % 8475871 + 1;
Z[2] = (x2 * 90123 + y2) % 8475871 + 1;
for(i = 3 ;i <= n * n ;i ++)
{
x = (12345 + x2 * 23456 + x1 * 34567 + x2 * x1 * 45678) % 5837501;
y = (56789 + y2 * 67890 + y1 * 78901 + y2 * y1 * 89012) % 9860381;
Z[i] = (x * 90123 + y) % 8475871 + 1;
x1 = x2 ,y1 = y2;
x2 = x ,y2 = y;
}
memset(list ,0 ,sizeof(list)) ,tot = 1;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
if(i == j) add(i ,j ,0);
else add(i ,j ,Z[(i - 1) * n + j]);
spfa(1 ,n);
__int64 min = INF;
for(i = 2 ;i <= n ;i ++)
if(min > s_x[i] % m)
min = s_x[i] % m;
printf("%I64d\n" ,min);
}
return 0;
}