測試點2不過的原因，是更新路徑條數(shù)的時候诞外，不是加上它前驅(qū)的所有路徑條數(shù)，而是只加一
純DIJSTRA實現(xiàn)
這道題做的真的好幸福啊灾票，因為是都沒怎么調(diào)峡谊，就做出來了，讓我對DIJSTRA的認識又進一步了

#include<cstdio>
#include<utility>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 26 * 26 * 26 + 5, INF = 0x3fffffff;
vector<pair<int, int> > graph[maxn];//first是id second是cost
int happyValue[maxn], level[maxn], dis[maxn], city_num, happy_sum[maxn], pre[maxn], path[maxn], star_id;//level用來記錄層數(shù)，最后層數(shù)最少的就是平均幸福值最低的
bool vis[maxn];
int getID(char* name) {
    int id = 0;
    for (int i = 0; i < 3; i++)
        id = id * 26 + name[i] - 'A';
    return id;
}
void print_name(int id) {
    char name[6]; name[3] = '\0';
    for (int i = 2; i >= 0; i--) {
        int temp = id % 26;
        id /= 26;
        name[i] = temp + 'A';
    }
    printf("%s", name);
}
void DIJSTRA(int source) {
    fill(dis, dis + maxn, INF);
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(pair<int, int>(0, source)); dis[source] = 0; path[source] = 1; level[source] = 0;
    pre[source] = source;
    for (int i = 0; i < city_num; i++) {
        if (q.empty())break;
        pair<int, int> temp = q.top(); q.pop();
        int u = temp.second; vis[u] = true;
        //print_name(u); printf(" ");
        for (int j = 0; j < graph[u].size(); j++) {
            int v = graph[u][j].first, cost = graph[u][j].second;
            //print_name(v); printf("\n");
            if (!vis[v]) {
                if (dis[v] > dis[u] + cost) {
                    level[v] = level[u] + 1;
                    dis[v] = dis[u] + cost;
                    happy_sum[v] = happy_sum[u] + happyValue[v];
                    pre[v] = u;
                    q.push(pair<int, int>(dis[v], v));
                    path[v] = path[u];
                }
                else if (dis[v] == dis[u] + cost) {
                    path[v] += path[u];
                    if (happy_sum[v] < happy_sum[u] + happyValue[v]) {
                        level[v] = level[u] + 1;
                        happy_sum[v] = happy_sum[u] + happyValue[v];
                        pre[v] = u;
                    }
                    else if (happy_sum[v] == happy_sum[u] + happyValue[v] && level[u] + 1 < level[v]) {//層數(shù)越少既们，那么快樂平均值越高
                        level[v] = level[u] + 1;
                        pre[v] = u;
                    }
                }
            }
        }
    }
}
void DFS(int source) {
    if (source == star_id) print_name(source);
    else {
        DFS(pre[source]);
        printf("->");
        print_name(source);
    }

}
int main() {
    char city1[6], city2[6], strdes[6];//最后這個用來記錄出發(fā)的地點
    int k, cost; scanf("%d %d %s", &city_num, &k, strdes); getchar();
    star_id = getID(strdes);
    for (int i = 1; i < city_num; i++) {
        scanf("%s", city1);
        scanf("%d", &happyValue[getID(city1)]);
    }
    for (int i = 0; i < k; i++) {
        scanf("%s %s %d", city1, city2, &cost); getchar();
        int id1 = getID(city1), id2 = getID(city2);
        graph[id1].push_back(pair<int, int>(id2, cost));
        graph[id2].push_back(pair<int, int>(id1, cost));
    }
    DIJSTRA(star_id);
    char end_name[] = "ROM";
    int end = getID(end_name);
    printf("%d %d %d %d\n", path[end], dis[end], happy_sum[end], happy_sum[end] / level[end]);
    DFS(end);printf("\n");
    
}