2014西安全国邀请赛——题目重现(感谢西工大+复旦 HDOJ 4849 Wow! Such City!

By | 05月08日
Advertisement

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

题目:

Wow! Such City!

Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 253 Accepted Submission(s): 89

Problem Description

Doge, tired of being a popular image on internet, is considering moving to another city for a new way of life.
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

Input

There 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.

Output

For each test case, output a single line containing a single integer: the number of minimal category.

Sample Input

3 10 1 2 3 4 4 20 2 3 4 5

Sample Output

1 10

题意:

让你求出一个n*n的矩阵,从0这个点出发,到其他点的最短距离。

解题思路:

单源最短路径,Dijkstra。ps:注意中间处理时x、y可能会超int。

代码:

#include <cstdio> #include <cstring> #include <limits.h> using namespace std;  const int MAXN = 1010; long long x[MAXN*MAXN], y[MAXN*MAXN], z[MAXN*MAXN]; int map[MAXN][MAXN], d[MAXN]; bool vis[MAXN]; int n, m, ans;  void Dijkstra(int s) {     memset(vis, false, sizeof(vis));     vis[s] = true;     for(int i = 0; i < n; i++)     {         d[i] = map[s][i];     }     d[s] = 0;     for(int i = 0; i < n - 1; i++)     {         int min = INT_MAX, k = -1;         for(int j = 0; j < n; j++)         {             if(!vis[j] && min > d[j])             {                 min = d[j];                 k = j;             }         }         vis[k] = true;         for(int j = 0; j < n; j++)         {             if(!vis[j] && d[k] + map[k][j] < d[j])             {                 d[j] = d[k] + map[k][j];             }         }     }    //printf("%d : n", s);     for(int i = 0; i < n; i++)     {         int tmp = d[i] % m;         if(i != s && tmp < ans)         {             ans = tmp;         }       //  printf("%d ", d[i]);     }    // puts(""); }  int main() {     while(~scanf("%d%d%I64d%I64d%I64d%I64d",                  &n, &m, &x[0], &x[1], &y[0], &y[1]))     {         int t = n * n;         for(int i = 2; i < t; i++)         {             x[i] = (12345 + x[i-1] * 23456 + x[i-2] * 34567 +                     x[i-1] * x[i-2] * 45678) % 5837501;             y[i] = (56789 + y[i-1] * 67890 + y[i-2] * 78901 +                     y[i-1] * y[i-2] * 89012) % 9860381;         }         for(int i = 0; i < t; i++)         {             z[i] = (x[i] * 90123 + y[i]) % 8475871 + 1;         }         for(int i = 0; i < n; i++)         {             for(int j = 0; j < n; j++)             {                 map[i][j] = (i == j ? 0 : z[i*n+j]);         //        printf("%d ", map[i][j]);             }          //   puts("");         }         ans = INT_MAX;         Dijkstra(0);         printf("%dn", ans);     }     return 0; }

Similar Posts:

  • HDU 5097 Page Rank(矩阵模拟)——2014上海全国邀请赛——题目重现(感谢上海大学提供题目)

    传送门 Page Rank Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 100000/100000 K (Java/Others)Total Submission(s): 346    Accepted Submission(s): 105 Problem Description Evaluation and rank of web pages is a hot topic for many internet companies

  • HDU5092 Seam Carving(2014上海全国邀请赛——题目重现)(DP)

    题意:给你一个n*m的矩阵,每一行取出一个数,使得这些数和最小,且相邻两行的数所在的列的差的绝对值不能超过1.如果不止一种取法,输出列序号最大的. 分析:数塔DP= =..多了一个数组来记录每一个节点的后继...因为要从上往下输出,所以我们从下往上递推,这样可以避免递归输出路径...注意要优先选取靠右的列... #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #

  • hdu 4576 robot 2013 ACM-ICPC杭州赛区全国邀请赛——题目重现-1001-robot

    题意:有一个机器人他的初始位置是1,在一个环形轨道上(轨道的长度n<=200),由于遥控器不太灵,机器人不太能准确的接受遥控的指令,遥控指令是让机器人顺时针或逆时针走w步,所以机器人有1/2的概率顺时针走w步,1/2的 概率逆时针走w步,题目就是要你算经过m(m<=1000000)次指令遥控后机器人最后停在某段轨道(L,R)的概率,这题我也没想出什么好办法,就暴力了,不断的WA,TLE,最后3500ms险过了(题目限时4000ms) 既然决定暴力,那么就是一步一步的算机器人走到轨道的某处的情况

  • 2014上海全国邀请赛1010(hdu 5099)

    Comparison of Android versions Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 67 Accepted Submission(s): 54 Problem Description As an Android developer, itˇs really not easy to figure out a newer

  • 2014西安邀请赛部分题解

    HDU 4848 Wow! Such Conquering! 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4848 题意及思路:有n个星球,现在你从1开始需要访问其他所有的星球.给你Txy表示从x到y的时间,再给n-1个Deadline表示第一次到星球2~n的最迟时间不能超过所给的Deadline.现在问你是否能在要求内访问所有的星球,如果可以输出最小的时间,否则输出-1. 主体思路是dfs,不过必须要进行剪枝,通过时间是否超过Deadline可

  • hdu4576 Robot 2013 ACM-ICPC杭州赛区全国邀请赛 1

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4576 模拟水题.我愣是做了几个小时,好几个小错误. ///2014.5.14 ///hdu4576 ///2013 ACM-ICPC杭州赛区全国邀请赛 1 #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #i

  • 腾讯2014软件开发笔试题目简答题

    腾讯2014软件开发笔试题目 -----9月21日,腾讯2014软件开发校招-简答题-广州 简答题: 1.请设计一个排队系统,能够让每个进入队伍的用户都能看到自己在 中所处的位置和变化.队伍可能随时有人加入和退出,当有人退出影响到用户的位置排名时需要即时反馈到用户. 2.A.B两个整数集合,设计一个算法求他们的交集,尽可能的高效. (博主能力有限,不是所有题目都会求解,第1题不是我的擅长,这里贴出来让大家知道腾讯的考题.我的重点放在第2题上面!) 第2题 题解(个人见解,仅供参考!) 思路1:排

  • 关于举办2014年全国高校IT骨干教师暑期培训班的通知

    各相关高校.院系: 为贯彻落实党的十八大关于全面深化教育改革的战略部署,深入学习领会习近平总书记系列重要讲话中关于教育教学改革的论述,结合目前高校 IT 教育教学实际,经研究决定,中国电子学会.中关村软件园人才基地.CSDN 和传智播客教育集团联合于 2014 年 7 月在京举办"2014 年全国高校 IT 骨干教师暑期培训班". 本次培训班将以提高教师综合素质为抓手,以推进产教深入融合为目标,探索高校师资培养创新机制,旨在为高校培养专业功底深.技术水平高.执教能力强.符合社会产业要求

  • 广州仁和会计培训学校告诉你:2014年全国各省市平均工资出炉了

    广州仁和会计培训学校告诉你:2014年全国各省市平均工资出炉了.2014年度即将过去,2015年度即将要来了,或许大家都对于自己的工资是比较关心的.最近网络上就流传一份据说由大数据统计出来的2014年度全国309城市平均工资单. 从中看到了很多古怪现象,比如二三线城市的平均工资竟然比一线城市(北上广)还高.这放到网上还不惊起骂声一片.又一想,本来就是" 大地方做小人物,小地方做大人物","有钱人"不分地域.仁者见仁智者见智,结论就免了,自行琢磨吧. 其实尚属正常,本

  • 2014西安三八妇女节活动:益智儿童剧《小吉普变变变》

    活动时间:2014年03月08日 15:00 - 2014年03月08日 17:00 活动地址:西安市 西安音乐厅 曲江新区雁南一路 活动介绍: 在日本,有一档二十多年来经久不衰的电视节目叫 <超级变变变>.它让小朋友们利用简单的道具,在很短的时间里模仿出我们身边熟悉的东西:花鸟虫鱼.电烫斗.面包机.电车.冲浪.礼花甚至是炸大虾无所不包,其丰富的想象力令人叹为观止,更是培养了孩子的创造力和创新能力.让小朋友们一定对自己身边的东西产生浓厚的兴趣,开动他们的小脑筋,学习怎样使这些东西变得活灵活现.

Tags: