本文主要是介绍HDU4849 Wow! Such City!(最短路，Djikstra)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Wow! Such City!
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)Total Submission(s): 1732 Accepted Submission(s): 581
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 C i, j (a positive integer) for traveling from city i to city j. Please note that C i, j may not equal to C j, 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 ≤ 10 6) 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:
C i, j is generated in the following way:
Given integers X 0, X 1, Y 0, Y 1, (1 ≤ X 0, X 1, Y 0, Y 1≤ 1234567), for k ≥ 2 we have
Xk = (12345 + X k-1 * 23456 + X k-2 * 34567 + X k-1 * X k-2 * 45678) mod 5837501
Yk = (56789 + Y k-1 * 67890 + Y k-2 * 78901 + Y k-1 * Y k-2 * 89012) mod 9860381
The for k ≥ 0 we have
Z k = (X k * 90123 + Y k ) mod 8475871 + 1
Finally for 0 ≤ i, j ≤ N - 1 we have
C i, j = Z i*n+j for i ≠ j
C i, j = 0 for i = j
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 C i, j (a positive integer) for traveling from city i to city j. Please note that C i, j may not equal to C j, 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 ≤ 10 6) 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:
C i, j is generated in the following way:
Given integers X 0, X 1, Y 0, Y 1, (1 ≤ X 0, X 1, Y 0, Y 1≤ 1234567), for k ≥ 2 we have
Xk = (12345 + X k-1 * 23456 + X k-2 * 34567 + X k-1 * X k-2 * 45678) mod 5837501
Yk = (56789 + Y k-1 * 67890 + Y k-2 * 78901 + Y k-1 * Y k-2 * 89012) mod 9860381
The for k ≥ 0 we have
Z k = (X k * 90123 + Y k ) mod 8475871 + 1
Finally for 0 ≤ i, j ≤ N - 1 we have
C i, j = Z i*n+j for i ≠ j
C i, 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,X 0,X 1,Y 0,Y 1.See the description for more details.
For each test case, there is only one line containing 6 integers N,M,X 0,X 1,Y 0,Y 1.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 10For the first test case, we have0 1 2 3 4 5 6 7 8 X 1 2 185180 788997 1483212 4659423 4123738 2178800 219267 Y 3 4 1633196 7845564 2071599 4562697 3523912 317737 1167849 Z 90127 180251 1620338 2064506 625135 5664774 5647950 8282552 4912390the cost matrix C is0 180251 16203382064506 0 56647745647950 8282552 0HintSo the minimal cost from city 0 to city 1 is 180251, while the distance to city 2 is 1620338. Given M = 10, city 1 and city 2 belong to category 1 and 8 respectively. Since only category 1 and 8 contain at least one city, the minimal one of them, category 1, is the desired answer to Doge’s question.
Source
2014西安全国邀请赛
Recommend
liuyiding | We have carefully selected several similar problems for you: 6018 6017 6016 6015 6014
思路：
比赛的时候这个题没有看懂，因为好多数字，其实这题就是一个标准的迪杰斯特拉。
唯一的坑点在建图上面，必须按照题目要求的建图方式来建图，就是上面那一连串的式子。
只要建好图以后，找一下从0点到各个点的距离对m取模的最小值就是答案
还是太浮躁了，以后要注意
代码：
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define N 1000+20
#define inf 0x3f3f3f3f
#define M 1000000+2000
#define LL long long
using namespace std;
LL n,m,x00,x11,y00,y11;
LL map[N][N],dis[N],vis[N];
LL xx[M],yy[M],zz[M];
void init()//注意建图的方式，要按照题目的要求进行
{for(LL i=0; i<n; i++){for(LL j=0; j<n; j++){map[i][j]=inf;}map[i][i]=0;}xx[0]=x00;xx[1]=x11;yy[0]=y00;yy[1]=y11;for(LL k=2; k<=n*n; k++){xx[k]=(12345+xx[k-1]*23456+xx[k-2]*34567+xx[k-1]*xx[k-2]*45678)%5837501;yy[k]=(56789+yy[k-1]*67890+yy[k-2]*78901+yy[k-1]*yy[k-2]*89012)%9860381;}for(LL k=0; k<=n*n; k++){zz[k]=(xx[k]*90123+yy[k])%8475871+1;}for(LL i=0; i<n; i++){for(LL j=0; j<n; j++){if(i==j)map[i][j]=0;elsemap[i][j]=zz[i*n+j];}}
}
void dj()
{LL minn,k=0;for(LL i=0; i<=n; i++){dis[i]=map[0][i];vis[i]=0;}dis[0]=0;for(LL j=0; j<n; j++){minn=inf;for(LL i=0; i<n; i++){if(!vis[i]&&minn>dis[i]){minn=dis[i];k=i;}}vis[k]=1;for(LL i=0; i<n; i++){if(!vis[i]&&dis[i]>dis[k]+map[k][i])dis[i]=dis[k]+map[k][i];}}return;
}void solve()
{LL minn=inf;for(LL i=1; i<n; i++){minn=min(minn,dis[i]%m);}printf("%lld\n",minn);
}
int main()
{while(~scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&x00,&x11,&y00,&y11)){init();//建图dj();//迪杰斯塔拉solve();//输出结果}return 0;
}
这篇关于HDU4849 Wow! Such City!(最短路，Djikstra)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
