PAT甲级练习 1087 All Roads Lead to Rome (30分) 字符串hash + dijkstra

阅读原文时间：2023年07月08日阅读：2

题目分析：

这题我在写的时候在PTA提交能过但是在牛客网就WA了一个点，先写一下思路留个坑

这题的简单来说就是需要找一条最短路->最开心->点最少（平均幸福指数自然就高了），由于本题给出的所有的城市的名称都是字符串（三个大写字母），所以我先将每个字符串计算一个hash值去代表每一个城市，接着就是用dijkstra算法去逐步判断各种情况，是直接用了一个dijkstra去计算，而没有说是先dijkstra算出最短距离再dfs所有的路径去找出最优解，因为我觉得这题局部最优就能反映到全局最优，也不知是不是想错了才在牛客上有一个点过不去QAQ…

本题代码：

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 using namespace std;
10
11 const int N = 3000;
12 const int M = 0x3f3f3f3f;
13 int mat[N][N];
14 int dist[N];
15 int vis[N];
16 int hap[N];
17 int get_hap[N]; //已知情况下到i点能获得的幸福值
18 int way[N]; //到达每个点有多少种走法
19 int num[N]; //到达i点需要走多少个点第一个sta不算
20 vector v[N];
21 int pre[N];
22 map mp;
23 int n, m, min_dist, max_hap;
24
25 int trans(string s){
26 int len = s.size();
27 int sum = 0;
28 for(int i = 0; i < len; i++){ 29 sum = sum * 10 + s[i] - 'A'; 30 } 31 return sum; 32 } 33 34 int minn(){ 35 int Min = M; 36 int k = -1; 37 for(int i = 0; i < 3000; i++){ 38 if(vis[i] == 0 && dist[i] < Min){ 39 Min = dist[i]; 40 k = i; 41 } 42 } 43 return k; 44 } 45 46 void out(int x){ 47 if(pre[x] == -1){ 48 cout<"< get_hap[j]){ //距离相同但是更快乐
77 get_hap[j] = get_hap[k] + hap[j];
78 pre[j] = k;
79 num[j] = num[k] + 1;
80 }else if(get_hap[k] + hap[j] == get_hap[j]){//距离相同且同样快乐则比较点的个数
81 if(num[k] + 1 < num[j]){ //点更少 82 pre[j] = k; 83 num[j] = num[k] + 1; 84 } 85 } 86 } 87 } 88 } 89 int en = trans("ROM"); 90 printf("%d %d %d %d\n", way[en], dist[en], get_hap[en], get_hap[en]/num[en]); 91 out(en); 92 printf("\n"); 93 } 94 95 int main(){ 96 scanf("%d%d", &n, &m); 97 string sta; 98 cin>>sta;
99 int st = trans(sta);
100 mp[st] = sta;
101 memset(vis, 0, sizeof(vis));
102 memset(hap, 0, sizeof(hap));
103 memset(mat, M, sizeof(mat));
104 memset(num, 0, sizeof(num));
105 memset(get_hap, 0, sizeof(get_hap));
106 memset(way, 0, sizeof(way));
107 for(int i = 1; i < n; i++){ 108 string s; 109 cin>>s;
110 int tt = trans(s);
111 mp[tt] = s;
112 int x;
113 scanf("%d", &x);
114 hap[tt] = x; //根据hash值锁定幸福值
115 }
116 for(int i = 1; i <= m; i++){ 117 string s1, s2; int x; 118 cin>>s1>>s2; scanf("%d", &x);
119 int t1 = trans(s1);
120 int t2 = trans(s2);
121 v[t1].push_back(t2);
122 v[t2].push_back(t1);
123 mat[t1][t2] = x;
124 mat[t2][t1] = x;
125 }
126 dijkstra(st);
127 return 0;
128 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章