The 'Heavenly Dragon Kingdom' has launched a metro tourism map to promote tourism. As long as tourists hold a tourism passport, they will receive special privileges when taking the metro. The fares will be charged according to the following three billing rules:
- The base fare is $10.
- The fare increases by $5 for every three stations passed.
- Transferring to different metro lines incurs an additional $5.
Using the example in the diagram, if the starting point is B1 the endpoint is G2, and the route taken is: B1-B2-B3-B4-G1-G2, the fare required is $20 (=10 + 51 + 5, where $10 is the base fare, $5 for passing through 5 stations, and $5 for transferring). If the route taken is: B1-B2-R1-R2-R3-G2, the fare required is $25 (=10 + 51 + 5*2, where $10 is the base fare, $5 for passing through 5 stations, and $10 for transferring to two different metro lines).
Now, please design a program that, when tourists decide on the starting and ending points of the metro, can calculate the fare for each tourist visiting here (if there are multiple routes available from the starting point to the ending point, please calculate the cheapest fare).
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains a positive integer N (1 ≤ N ≤ 500), where N represents the following N sets of information about the current metro stations. From the second line to the N+1 line, each line represents information about the connectivity between any two metro stations. Each station is named with an uppercase English letter followed by a number, where the initial uppercase English letter represents the metro line it belongs to, and the number m is a positive integer less than or equal to 100 (1 ≤ M ≤ 100). There is a space between the two stations, and connectivity between the two stations is bidirectional. The N+2 line represents the starting point and the destination of the planned route, separated by a single space. | Please output a numerical value representing the cheapest fare from the starting point to the destination. |
| 11 B1 B2 B2 B3 B3 B4 B4 B5 B4 G1 G1 G2 G2 G3 R1 R2 R2 R3 B2 R1 R3 G2 B1 G2 | 20 |
| 12 R1 R2 R2 R3 R3 R4 R4 R5 R5 R6 R6 R7 R7 B1 R7 Y1 Y1 B1 Y1 R1 Y1 G1 G1 R1 G1 B1 | 20 |
Thought Process
Use a Map to record which stations each station can reach, and use a Vector to store stations. Since it's bidirectional, the destination station should also store the starting station. Use BFS to find the route with the lowest fare. You can use a Map to store the fare for each station. If the same station is reached again, compare the fares of different routes. Finally, output the Map value of the destination station.
Sample Code－ZeroJudge A586: Metro Pricing
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int N;
map<string, vector<string>>MAP;
map<string, pair<int, int>>info;
void BFS(vector<string>start)
{
if (start.size() == 0) return;
vector<string>newStart;
for (int i = 0; i<start.size(); i++)
{
vector<string>next = MAP[start[i]];
for (int j = 0; j<next.size(); j++)
{
int step = info[start[i]].first+1, line = info[start[i]].second;
if (start[i][0] != next[j][0]) line++;
if (info[next[j]].first == 0 && info[next[j]].second == 0)
{
info[next[j]].first = step;
info[next[j]].second = line;
newStart.push_back(next[j]);
continue;
}
int oldmoney = 5*(info[next[j]].first/3) + 10 + (5*info[next[j]].second);
int newmoney = 5*(step/3) + 10 + (5*line);
if (newmoney < oldmoney)
{
info[next[j]].first = step;
info[next[j]].second = line;
newStart.push_back(next[j]);
continue;
}
}
}
BFS(newStart);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i<N; i++)
{
string a, b;
cin >> a >> b;
MAP[a].push_back(b);
MAP[b].push_back(a);
}
string start, finish;
cin >> start >> finish;
info[start].first = 0;
info[start].second = 0;
vector<string>v;
v.push_back(start);
BFS(v);
cout << 5*(info[finish].first/3) + 10 + (5*info[finish].second) << "\n";
}
//ZeroJudge A586
//Dr. SeanXD