问题描述
我写的代码有有两个个测试点没有通过，自己翻来覆去的没看出哪里错了，求大神指点一下。https://www.nowcoder.com/pat/...
#include <stdio.h>#include <vector>#include <string.h>#define MaxNum 205using namespace std;typedef struct E { int next; int cost;} Edge;vector<Edge> 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 %dn', city[i], happy[i]); // } endnum = citytonum(city, endcity, n); //printf('endnum = %dn', 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 = %dn', newp);for(j = 0; j < edge[newp].size(); j++) { num1 = edge[newp][j].next; cost = edge[newp][j].cost; //printf('num1 = %dn', 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 = %dn', 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 %dn', 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;}
问题解答
回答1：这个是正确代码。
#include <string>#include <map>#include <iostream>#include <cstring> 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<string, int> name_to_num;map<int, string> 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]<minn) {index = i;minn = dis[i]; }}if (index == -1){ break;}vi[index] = true;for (int j = 0; j < n; ++ j){ if (dis[j] > 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;}
