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

これは正しいコードです。

リーリー