1087 All Roads Lead to Rome 30 ★★☆☆

Jianpan Gun文章访问量:

github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：★★☆☆ 关键词：Dijkstra + DFS

题目

1087 All Roads Lead to Rome （30） Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

Input Specification: Each input file contains one test case. For each case, the first line contains 2 positive integers N (2≤N≤200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N−1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format City1 City2 Cost. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

Output Specification: For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommanded. If such a route is still not unique, then we output the one with the maximum average happiness -- it is guaranteed by the judge that such a solution exists and is unique.

Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommanded route. Then in the next line, you are supposed to print the route in the format City1->City2->...->ROM.

Sample Input: 6 7 HZH ROM 100 PKN 40 GDN 55 PRS 95 BLN 80 ROM GDN 1 BLN ROM 1 HZH PKN 1 PRS ROM 2 BLN HZH 2 PKN GDN 1 HZH PRS 1 Sample Output: 3 3 195 97 HZH->PRS->ROM

大意

求最短路径，如果最短路径有多个，则选取 happy 值最大的路径，如果还有多个，则输出平均 happy 值最大的路径

思路

  1. 这是一个典型的Dijkstra题，但很明显不是裸Dijkstra,有第二变量；
  2. 所以需要我们用vector<int> pre[MAXN]存储最短路径, 然后根据 DFS 进行遍历；
  3. 本题烦在还评定标准多，输出参数多, 调试可能会比较费劲；

code

#include <iostream>
#include <map>
#include <vector>

using namespace std;

const int INF = 0x3fffffff;
const int MAXN = 209;

struct node {
  int next, spend;
};

std::vector<node> v[MAXN];
bool vis[MAXN] = {false};
std::vector<string> city;
std::vector<int> happy, pre[MAXN], path, temppath, totalhappy;
std::map<string, int> string2int;
int n, k, happiness, rom, d[MAXN], optvalue = 0, avg = 0;

void Dijkstra(int start) {
  fill(d, d + MAXN, INF);
  d[start] = 0;
  for (int i = 0; i < n; ++i) {
    int u = -1, MIN = INF;
    for (int j = 0; j < n; ++j) {
      if (!vis[j] && d[j] < MIN) {
        u = j;
        MIN = d[j];
      }
    }
    if (u == -1) return;
    vis[u] = true;
    for (int j = 0; j < v[u].size(); ++j) {
      int temp = v[u][j].next;
      if (!vis[temp]) {
        if (d[u] + v[u][j].spend < d[temp]) {
          d[temp] = d[u] + v[u][j].spend;
          pre[temp].clear();
          pre[temp].push_back(u);
        } else {
          pre[temp].push_back(u);
        }
      }
    }
  }
}

void dfs(int now, int temphappy) {
  temppath.push_back(now);
  if (!now) {
    // cout << optvalue << ' ' << temphappy + happy[now] << endl;
    if (optvalue < temphappy + happy[now] ||
        (optvalue == temphappy + happy[now] && temppath.size() < path.size())) {
      optvalue = temphappy + happy[now];
      avg = optvalue / (temppath.size() - 1);
      path = temppath;
    }
    totalhappy.push_back(temphappy + happy[now]);
    temppath.pop_back();
    return;
  }
  for (int i = 0; i < pre[now].size(); ++i) {
    dfs(pre[now][i], temphappy + happy[pre[now][i]]);
  }
  temppath.pop_back();
}

int main(int argc, char const *argv[]) {
  string str, str2;
  cin >> n >> k >> str;
  city.push_back(str);
  happy.push_back(0);
  string2int[str] = 0;
  for (int i = 1; i < n; ++i) {
    cin >> str >> happiness;
    happy.push_back(happiness);
    city.push_back(str);
    string2int[str] = i;
    if (str == "ROM") rom = i;
  }
  for (int i = 0; i < k; ++i) {
    node temp;
    cin >> str >> str2 >> temp.spend;
    temp.next = string2int[str2];
    v[string2int[str]].push_back(temp);
    temp.next = string2int[str];
    v[string2int[str2]].push_back(temp);
  }
  Dijkstra(0);
  dfs(rom, happy[rom]);
  cout << totalhappy.size() << ' ' << d[rom] << ' ' << optvalue << ' ' << avg
       << endl;
  for (int i = path.size() - 1; i >= 1; --i) cout << city[path[i]] << "->";
  cout << "ROM";
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
You can use this BibTex to reference this blog if you find it useful and want to quote it.
CodingPAT
Prev
2018 PKU RW entrance
postNav_next
1086 Tree Traversals Again 25 ☆☆★