c++ - 写的算法哪里错了？

Question

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

#include <stdio.h>
#include <vector>
#include <string.h>
#define MaxNum 205

using 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 %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;
}

Answer 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;
}