c++ - 写的算法哪里错了？-Fragen und Antworten zum chinesischen PHP-Netzwerk

我写的代码有有两个个测试点没有通过，自己翻来覆去的没看出哪里错了，求大神指点一下。
https://www.nowcoder.com/pat/...

#include  #include  #include  #define MaxNum 205 using namespace std; typedef struct E { int next; int cost; } Edge; vector edge[MaxNum]; int mark[MaxNum]; char city[MaxNum][4]; int happy[MaxNum]; int counthappy[MaxNum]; int Dis[MaxNum]; int path[MaxNum]; int citytonum(char city[][4], char str[], int n) { int i; for(i = 0; i < n; i++) { if(strcmp(str, city[i]) == 0) { break; } } return i; } int countcity[MaxNum]; int main() { int n, k; int startnum = 0; int endnum; char starcity[4]; char endcity[4] = "ROM"; scanf("%d %d %s", &n, &k, starcity); int i, j; strcpy(city[0], starcity); happy[0] = 0; for(i = 1; i < n; i++) { scanf("%s %d", city[i], &happy[i]); } for(i = 0; i <= n; i++) { edge[i].clear(); } // for(i = 1; i < n; i++) { // printf("%s %d\n", city[i], happy[i]); // } endnum = citytonum(city, endcity, n); //printf("endnum = %d\n", endnum); int record1, record2; int cost; char restr1[4], restr2[4]; for(i = 0; i < k; i++) { scanf("%s %s %d", restr1, restr2, &cost); record1 = citytonum(city, restr1, n); record2 = citytonum(city, restr2, n); Edge tmp; tmp.cost = cost; tmp.next = record2; edge[record1].push_back(tmp); tmp.next = record1; edge[record2].push_back(tmp); } for(i = 0; i <= n; i++) { Dis[i] = -1; mark[i] = 0; path[i] = -1; counthappy[0] = 0; } Dis[0] = 0; mark[0] = 1; int newp = 0; counthappy[0] = 0; int num1; countcity[0] = 0; for(i = 0; i < n; i++) { //printf("newp = %d\n", newp); for(j = 0; j < edge[newp].size(); j++) { num1 = edge[newp][j].next; cost = edge[newp][j].cost; //printf("num1 = %d\n", num1); if(mark[num1] == 1) continue; if(Dis[num1] == -1 || Dis[num1] > Dis[newp] + cost || Dis[num1] == Dis[newp] + cost && counthappy[num1] < counthappy[newp] + happy[num1] || Dis[num1] == Dis[newp] + cost && counthappy[num1] == counthappy[newp] + happy[num1] && countcity[num1] > countcity[newp] + 1) { Dis[num1] = Dis[newp] + cost; counthappy[num1] = counthappy[newp] + happy[num1]; path[num1] = newp; countcity[num1] = countcity[newp] + 1; } } int mindis = 999999999; int minhappy = 999999999; int citynum = 999999999; for(j = 1; j < n; j++) { if(mark[j] == 1) continue; if(Dis[j] == -1) continue; if(Dis[j] < mindis || Dis[j] == mindis && counthappy[j] < minhappy || Dis[j] == mindis && counthappy[j] == minhappy && countcity[j] < citynum) { mindis = Dis[j]; minhappy = counthappy[j]; citynum = countcity[j]; newp = j; //printf("newp = %d\n", newp); } } mark[newp] = 1; } int countleastcity = 0; for(j = 0; j < edge[endnum].size(); j++) { int num2 = edge[endnum][j].next; cost = edge[endnum][j].cost; if(Dis[num2] + cost == Dis[endnum]) { countleastcity++; } } printf("%d %d %d %d\n", countleastcity, Dis[endnum], counthappy[endnum], counthappy[endnum] / countcity[endnum]); int tpath[MaxNum]; int p = 0; for(j = endnum; j != -1; j = path[j]) { tpath[p] = j; p++; } for(j = p - 1; j >= 0; j--) { i = tpath[j]; printf("%s", city[i]); if(j != 0) { printf("->"); } } return 0; }

#include #include #include #include using namespace std; const int INF = 2100000000; const int MAX = 205; int n, K; bool vi[MAX]; int dis[MAX]; int cost[MAX][MAX]; int happiness[MAX], final_happiness[MAX]; int pre[MAX]; int pre_city_cnt[MAX]; int road_cnt[MAX]; map name_to_num; map num_to_name; void init() { string name1, name2; int dist; cin >> n >> K >> name1; name_to_num[name1] = 0; num_to_name[0] = name1; happiness[0] = final_happiness[0] = 0; for (int i = 1; i < n; ++ i) { cin >> name1; name_to_num[name1] = i; num_to_name[i] = name1; cin >> happiness[i]; } memset(vi, false, sizeof(vi)); memset(road_cnt, 0, sizeof(road_cnt)); memset(pre_city_cnt, 0, sizeof(pre_city_cnt)); for (int i = 0; i < n; ++ i) { dis[i] = INF; for (int j = 0; j < n; ++ j) { cost[i][j] = INF; } } for (int i = 0; i < K; ++ i) { cin >> name1 >> name2 >> dist; cost[name_to_num[name1]][name_to_num[name2]] = dist; cost[name_to_num[name2]][name_to_num[name1]] = dist; } } void dijkstra() { dis[0] = 0; road_cnt[0] = 1; for (int k = 0; k < n; ++ k) { int index = -1; int minn = INF; for (int i = 0; i < n; ++ i) { if (vi[i]==false && dis[i] dis[index] + cost[index][j]) { road_cnt[j] = road_cnt[index]; dis[j] = dis[index] + cost[index][j]; final_happiness[j] = final_happiness[index] + happiness[j]; pre_city_cnt[j] = pre_city_cnt[index] + 1; pre[j] = index; } else if (dis[j] == dis[index] + cost[index][j]) { road_cnt[j] += road_cnt[index]; if (final_happiness[j] < final_happiness[index] + happiness[j]) { final_happiness[j] = final_happiness[index] + happiness[j]; pre_city_cnt[j] = pre_city_cnt[index] + 1; pre[j] = index; } else if (final_happiness[j] == final_happiness[index] + happiness[j] && pre_city_cnt[j] > pre_city_cnt[index] + 1) { pre_city_cnt[j] = pre_city_cnt[index] + 1; pre[j] = index; } } } } } void print(int city) { if (city == 0) { int dest = name_to_num[string("ROM")]; cout << road_cnt[dest] << " " << dis[dest] << " " << final_happiness[dest] << " " << final_happiness[dest] / pre_city_cnt[dest] << endl; cout << num_to_name[0]; } else { print(pre[city]); cout << "->" << num_to_name[city]; } } int main() { init(); dijkstra(); print( name_to_num[string("ROM")] ); return 0; }