hdu4849 最短路

hdu4849 最短路

题意：       让你求0到所有点最短路中对m取余最小的那个数。 思路：

简单题，直接根据题目给的公式把z求出来，然后建边，然后最短路，然后枚举每一个点对m取余记录最小，然后输出答案，然后ac.

#include#include#define N_node 1111#define N_edge 1111111#define INF 1000000000using 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; queueq; 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; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。