In his country there are N (2 ≤N≤ 1000) cities labeled 0 . . . N - 1.
He is currently in city 0. Meanwhile, for each pair of cities, there
exists a road connecting them, costing Ci,j (a positive integer) for traveling from city i to city j. Please note that Ci,j may not equal to Cj,i for any given i ≠ j.
Doge is carefully examining the cities: in fact he will divide cities (his current city 0 is NOT included) into M (2 ≤ M ≤ 106)
categories as follow: If the minimal cost from his current city
(labeled 0) to the city i is Di, city i belongs to category numbered Di mod M.Doge wants to know the “minimal” category (a category with minimal number) which contains at least one city.
For example, for a country with 4 cities (labeled 0 . . . 3, note
that city 0 is not considered), Doge wants to divide them into 3
categories. Suppose category 0 contains no city, category 1 contains
city 2 and 3, while category 2 contains city 1, Doge consider category 1
as the minimal one.
Could you please help Doge solve this problem?
Note:
Ci,j is generated in the following way:
Given integers X0, X1, Y0, Y1, (1 ≤ X0, X1, Y0, Y1≤ 1234567), for k ≥ 2 we have
Xk = (12345 + Xk-1 * 23456 + Xk-2 * 34567 + Xk-1 * Xk-2 * 45678) mod 5837501
Yk = (56789 + Yk-1 * 67890 + Yk-2 * 78901 + Yk-1 * Yk-2 * 89012) mod 9860381
The for k ≥ 0 we have
Zk = (Xk * 90123 + Yk ) mod 8475871 + 1
Finally for 0 ≤ i, j ≤ N - 1 we have
Ci,j = Zi*n+j for i ≠ j
Ci,j = 0 for i = j
For each test case, there is only one line containing 6 integers N,M,X0,X1,Y0,Y1.See the description for more details.
# include<iostream>
# include<cstdio>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std;
const int INF=1<<30;
int n,m;
long long x[1001005],y[1001005],z[1001005];
int a[1005][1005],dis[1005];
void init()
{
for(int i=2;i<n*n;++i)
x[i]=(12345+((x[i-1]%5837501)*23456)%5837501+((x[i-2]%5837501)*34567)%5837501+(((x[i-1]%5837501)*(x[i-2]%5837501))%5837501)*45678)%5837501;
for(int i=2;i<n*n;++i)
y[i]=(56789+((y[i-1]%9860381)*67890)%9860381+((y[i-2]%9860381)*78901)%9860381+(((y[i-1]%9860381)*(y[i-2]%9860381))%9860381)*89012)%9860381;
for(int i=0;i<n*n;++i)
z[i]=(((x[i]%8475871)*90123+y[i])%8475871+1)%8475871;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
a[i][j]=(i==j)?0:z[i*n+j];
}
}
void spfa()
{
fill(dis,dis+n,INF);
dis[0]=0;
queue<int>q;
q.push(0);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=1;i<n;++i){
if(dis[i]>dis[u]+a[u][i]){
dis[i]=dis[u]+a[u][i];
q.push(i);
}
}
}
}
int main()
{
while(~scanf("%d%d%lld%lld%lld%lld",&n,&m,&x[0],&x[1],&y[0],&y[1]))
{
init();
spfa();
int ans=m;
for(int i=1;i<n;++i)
ans=min(ans,dis[i]%m);
printf("%d\n",ans);
}
return 0;
}
HDU-4849 Wow! Such City! (单源最短路)的更多相关文章
-
HDU 4849 Wow! Such City!陕西邀请赛C(最短路)
HDU 4849 Wow! Such City! 题目链接 题意:依照题目中的公式构造出临接矩阵后.求出1到2 - n最短路%M的最小值 思路:就依据题目中方法构造矩阵,然后写一个dijkstra,利 ...
-
HDU 4849 - Wow! Such City!
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others) Input There ar ...
-
最短路模板(Dijkstra &; Dijkstra算法+堆优化 &; bellman_ford &; 单源最短路SPFA)
关于几个的区别和联系:http://www.cnblogs.com/zswbky/p/5432353.html d.每组的第一行是三个整数T,S和D,表示有T条路,和草儿家相邻的城市的有S个(草儿家到 ...
-
[ACM_图论] Domino Effect (POJ1135 Dijkstra算法 SSSP 单源最短路算法 中等 模板)
Description Did you know that you can use domino bones for other things besides playing Dominoes? Ta ...
-
用scheme语言实现SPFA算法(单源最短路)
最近自己陷入了很长时间的学习和思考之中,突然发现好久没有更新博文了,于是便想更新一篇. 这篇文章是我之前程序设计语言课作业中一段代码,用scheme语言实现单源最段路算法.当时的我,花了一整天时间,学 ...
-
单源最短路_SPFA_C++
当我们需要求一个点到其它所有点的最短路时,我们可以采用SPFA算法 代码特别好写,而且可以有环,但是不能有负权环,时间复杂度是O(α(n)n),n为边数,α(n)为n的反阿克曼函数,一般小于等于4 模 ...
-
【UVA1416】(LA4080) Warfare And Logistics (单源最短路)
题目: Sample Input4 6 10001 3 21 4 42 1 32 3 33 4 14 2 2Sample Output28 38 题意: 给出n个节点m条无向边的图,每条边权都为正.令 ...
-
【算法系列学习】Dijkstra单源最短路 [kuangbin带你飞]专题四 最短路练习 A - Til the Cows Come Home
https://vjudge.net/contest/66569#problem/A http://blog.csdn.net/wangjian8006/article/details/7871889 ...
-
模板C++ 03图论算法 1最短路之单源最短路(SPFA)
3.1最短路之单源最短路(SPFA) 松弛:常听人说松弛,一直不懂,后来明白其实就是更新某点到源点最短距离. 邻接表:表示与一个点联通的所有路. 如果从一个点沿着某条路径出发,又回到了自己,而且所经过 ...
随机推荐
-
Reverse Core 第一部分 代码逆向技术基础
@date: 2016/10/14 <逆向工程核心原理>笔记 记录书中较重要的知识,方便回顾 ps. 因有一些逆向基础,所以我本来就比较熟悉的知识并未详细记录 第一章 关于逆向工程 目标, ...
-
JS 拼接字符串数组
1.格式1 1.1例子 [ {name: '北京',value: Math.round(Math.random()*1000)}, {name: '天津',value: Math.round(Math ...
-
nutch-2.2.1 hadoop-1.2.1 hbase-0.92.1 集群部署
国内私募机构九鼎控股打造APP,来就送 20元现金领取地址:http://jdb.jiudingcapital.com/phone.html 内部邀请码:C8E245J (不写邀请码,没有现金送) 国 ...
-
Tomcat启动时为什么要配置CATALINA_HOME环境变量??
CATALINA_HOME的值被设为Tomcat的安装目录,如果环境变量CATALINA_HOME已经存在,则通过这个环境变量调用bin目录下的“catalina.bat start”命令 1.Tom ...
-
Mysql之CentOS初探
1. 卸载mysql 查看CentOS是否已经安装mysql数据库 rpm -qa | grep mysqlrpm -qa | grep MySQL 如果有,则卸载 // --nodeps表示强制rp ...
-
jquery系列教程2-style样式操作全解
全栈工程师开发手册 (作者:栾鹏) 快捷链接: jquery系列教程1-选择器全解 jquery系列教程2-style样式操作全解 jquery系列教程3-DOM操作全解 jquery系列教程4-事件 ...
-
time函数获取时间与本地时间不一致
修改php.ini,将“date.timezone”项修改为“date.timezone = PRC”. 大陆内地可用的值是:Asia/Chongqing ,Asia/Shanghai ,Asia/U ...
-
PHP中被忽略的性能优化利器:生成器
如果是做Python或者其他语言的小伙伴,对于生成器应该不陌生.但很多PHP开发者或许都不知道生成器这个功能,可能是因为生成器是PHP 5.5.0才引入的功能,也可以是生成器作用不是很明显.但是,生成 ...
-
cobaltstrike安装加破解教程+使用教程
1.先安装java环境= = 1. 下载1.8u121的JAVA JDK (新的java JDK不稳定)!!原因:https://blog.cobaltstrike.com/2017/04/26/ja ...
-
sql server两个时间段内,求出周末的量
公司有个表记录了出差(加班)的初始时间和截止时间,现在要计算出加班时间,之前的设计并没有考虑到这部分,因此本人通过sql重新计算周末数 表formmain starttime endtime 使用游标 ...