个人练习-PAT甲级-1087 All Roads Lead to Rome_综合

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805379664297984

虽然考完了，但闲着没事也做一道。Dijkstra题，除了最短路径外还要满足搜集的快乐点数以及平均快乐点数最高。

一些类：
Route类的path成员包含路径的数组（每个城市用id表示，起点id为0），ttl成员表示该走路径可获得的快乐点数。

class City {
    
public:string name;int hpp;
};class Route {
    
public:vector<int> path;int ttl;
};

读取数据，给每个城市编号，并将其存入一个mapname2idx中，通过名字可以获得id

    scanf("%d %d", &N, &K);cty.resize(N);cin >> cty[0].name;cty[0].hpp = 0;name2idx[cty[0].name] = 0;for (int i = 1; i < N; i++) {
    cin >> cty[i].name >> cty[i].hpp;name2idx[cty[i].name] = i;}

Dijkstra，输入s为起点编号。注意在dis[w] == g[v][w] + dis[v]时，虽然不用更新最短距离，但也要把pre[]数组赋值好。因为两条路径暂时的cost是相同的，还无法区分优劣。

void Dijkstra(int s) {
    dis[s] = 0;while (1) {
    int v = -1;int min_dis = MAXD;for (int i = 0; i < N; i++) {
    if (!known[i]) {
    if (dis[i] < min_dis) {
    min_dis = dis[i];v = i;}}}if (v < 0)break;known[v] = true;for (int w = 0; w < N; w++) {
    if (!known[w]) {
    if (g[v][w] < MAXD) {
    if (dis[w] > g[v][w] + dis[v]) {
    dis[w] = g[v][w] + dis[v];pre[w].clear();pre[w].push_back(v);}else if (dis[w] == g[v][w] + dis[v])pre[w].push_back(v);}}}}
}

根据pre[]数组来设置路径，实际上就是把所有cost最低的路径都放入rt数组中，这个递归过程比较容易写错，要特别注意。
当下一个城市的选择有多个时，要给rt[]拓展空间。
特别注意sz变量绝不能用rt.size()替换，因为在用到这个sz之前，rt.size()就改变了，所以在它改变前先存下来。

void setRoute(int pos, int now) {
    rt[pos].path.push_back(now);rt[pos].ttl += cty[now].hpp;if (pre[now].size() > 0) {
    for (int j = 0; j < pre[now].size() - 1; j++) {
    Route tmp = rt[pos];rt.push_back(tmp);}}int sz = rt.size();for (int j = 0; j < pre[now].size(); j++) {
    if (j == 0)setRoute(pos, pre[now][j]);elsesetRoute(sz - j, pre[now][j]);}}

因为只需找出最优的一条路径，我们不要排序，仅做一次遍历即可。

    Route best_r = rt[0];for (int i = 1; i < rt.size(); i++) {
    if (!cmp(best_r, rt[i])) {
    best_r = rt[i];}}

最后路径记得反向输出才是从起点到终点的顺序

    printf("%d %d %d %d\n", rt.size(), cost, best_r.ttl, best_r.ttl / (best_r.path.size()-1));for (int i = best_r.path.size()-1; i >= 0; i--) {
    if (i != best_r.path.size() - 1)printf("->");cout << cty[best_r.path[i]].name;}

完整代码

#include <iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<map>
#include<string.h>
#include<string>using namespace std;const int MAXD = 99999999;class City {
    
public:string name;int hpp;
};class Route {
    
public:vector<int> path;int ttl;
};int N, K;
map<string, int> name2idx;
int g[201][201];
vector<vector<int>> pre;
bool known[201];
int dis[201];
vector<Route> rt;
vector<City> cty;void Init() {
    rt.resize(1);rt[0].ttl = 0;pre.resize(N);for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++)g[i][j] = MAXD;}
}void Reset() {
    for (int i = 0; i < N; i++) {
    dis[i] = MAXD;known[i] = false;}
}void Dijkstra(int s) {
    dis[s] = 0;while (1) {
    int v = -1;int min_dis = MAXD;for (int i = 0; i < N; i++) {
    if (!known[i]) {
    if (dis[i] < min_dis) {
    min_dis = dis[i];v = i;}}}if (v < 0)break;known[v] = true;for (int w = 0; w < N; w++) {
    if (!known[w]) {
    if (g[v][w] < MAXD) {
    if (dis[w] > g[v][w] + dis[v]) {
    dis[w] = g[v][w] + dis[v];pre[w].clear();pre[w].push_back(v);}else if (dis[w] == g[v][w] + dis[v])pre[w].push_back(v);}}}}
}bool cmp(Route x, Route y) {
    if (x.ttl != y.ttl)return x.ttl > y.ttl;elsereturn x.path.size() < y.path.size();
}void setRoute(int pos, int now) {
    rt[pos].path.push_back(now);rt[pos].ttl += cty[now].hpp;if (pre[now].size() > 0) {
    for (int j = 0; j < pre[now].size() - 1; j++) {
    Route tmp = rt[pos];rt.push_back(tmp);}}int sz = rt.size();for (int j = 0; j < pre[now].size(); j++) {
    if (j == 0)setRoute(pos, pre[now][j]);elsesetRoute(sz - j, pre[now][j]);}}int main() {
    scanf("%d %d", &N, &K);cty.resize(N);cin >> cty[0].name;cty[0].hpp = 0;name2idx[cty[0].name] = 0;for (int i = 1; i < N; i++) {
    cin >> cty[i].name >> cty[i].hpp;name2idx[cty[i].name] = i;}Init();for (int i = 0; i < K; i++) {
    string c1, c2;int dis;cin >> c1 >> c2 >> dis;g[name2idx[c1]][name2idx[c2]] = dis;g[name2idx[c2]][name2idx[c1]] = dis;}Reset();Dijkstra(0);int now = name2idx["ROM"];setRoute(0, now);Route best_r = rt[0];for (int i = 1; i < rt.size(); i++) {
    if (!cmp(best_r, rt[i])) {
    best_r = rt[i];}}int cost = 0;for (int i = 0; i < best_r.path.size()-1; i++) {
    cost += g[best_r.path[i]][best_r.path[i+1]];}printf("%d %d %d %d\n", rt.size(), cost, best_r.ttl, best_r.ttl / (best_r.path.size()-1));for (int i = best_r.path.size()-1; i >= 0; i--) {
    if (i != best_r.path.size() - 1)printf("->");cout << cty[best_r.path[i]].name;}return 0;
}