A group of judges must get together to judge a contest held in a particular city, and they need to figure out the cheapest way of renting cars in order to get everyone to the contest. They observed that it might be cheaper if several judges share a rental car during all or part of the trip, thus reducing the overall cost. Your task is to identify the routes the judges should take in order to minimize the total cost of their car rentals.
We will make the following assumptions:
- The cost of a rental car is proportional to the distance it is driven. There are no charges for more than one occupant in the car, fuel, insurance, or leaving the car in a city other than that in which it was rented.
- All rental cars are billed at the same rate per mile.
- A rental car can accommodate any number of passengers.
- At most one road directly connects any pair of cities. Each road is two-way and has an integer length greater than zero.
- There is at least one route from every judge's starting city to the city in which the contest is held.
- All judges whose routes to the contest take them from or through the same city travel from that city to the contest together. (A judge might arrive at a city in one car and leave that city in a different car.)
The input contains several test cases. Each test case includes a route map, the destination city where the contest is being held, and the cities where the judges are initially located.
Each case appears in the input as a list of integers separated by blanks and/or ends of lines. The order and interpretation of the integers in each case is as follows:
- NC-the number of cities that appear in the route map; this will be no larger than 20.
- DC-the number of the destination city, assuming the cities are numbered 1 to NC.
- NR-the number of roads in the route map. Each road connects a distinct pair of cities.
- For each of the NR roads, three integers C1, C2, and DIST. C1 and C2 identify two cities connected by a road, and DIST gives the distance between these cities along that road.
- NJ-the number of judges. This number will be no larger than 10.
- NJ-integers, one for each judge each of these is a city number identifying the initial location of that judge.
The data for the last case will be followed by a line consisting of the integer `-1'.
For each test case, display the case number (1, 2,...) and the shortest total distance traveled by the rental cars conveying the judges to the contest. Then display the list of routes used by the judges, each route on a separate line, in the same order as the ordering of starting cities given in the input. Each route consists of the cities that the corresponding judge must visit, listed in the order in which they are visited, starting with the judge's starting city and ending with the contest city.Any other cities along the route are listed in the order in which they are visited during the judge's travels. Separate the numbers in the route with `-', and precede each route by three spaces.
If multiple sets of routes have the same minimum distance, choose a set that requires the fewest number of cities. If several sets of cities of the same cardinality may be used, choose the set that comes lexicographically first when ordered by city number (e.g., {2, 3, 6} rather than {2, 10, 5}). If multiple routes are still available, output any set of routes that meets the requirements.
Follow the format of the sample output.
5 3 5 1 2 1 2 3 2 3 4 3 4 5 1 2 4 2 2 5 1 4 4 3 1 3 1 2 3 2 3 4 2 2 1 2 3 3 3 1 2 2 1 3 3 2 3 1 2 2 1 -1
Case 1: distance = 6 5-4-2-3 1-2-3 Case 2: distance = 5 1-3-4 2-3-4 Case 3: distance = 3 2-3 1-2-3
目描述：
法官要到某城市加，他可以共同搭少用。
而每一台可以容限多人，最少花何，且出每法官的移情。
如果最少花有多，找一最少城市使用，再相同，找一字典最小的。
如果是有多路，任何一都可以。
目解法：
事上目要找的是不是所有的最小生成，而是要找法官起始位置和目的地都要在上。
好像是 NP problem，的英文名忘了。
不由於很少，可以哪些使用在上，再做一棵 MST。
出路， MST 以目的地 root 整理成一有根即可。
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
int x, y, cost;
bool operator<(const edge &a) const {
return cost < a.cost;
}
};
vector<int> g[25];
edge E[1024];
int parent[25];
int findp(int x) {
return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
int main() {
int N, D, R, NJ;
int J[25], cases = 0;
int i, j, k;
int x, y, v;
while(scanf("%d %d %d", &N, &D, &R) == 3) {
D--;
for(i = 0; i < N; i++)
g[i].clear();
for(i = 0; i < R; i++) {
scanf("%d %d %d", &x, &y, &v);
x--, y--;
g[x].push_back(y);
g[y].push_back(x);
E[i].x = x, E[i].y = y, E[i].cost = v;
}
scanf("%d", &NJ);
int must = 1<<D;
for(i = 0; i < NJ; i++) {
scanf("%d", &J[i]);
J[i]--;
must |= 1<<J[i];
}
sort(E, E+R);
// process brute force + MST
int allstate = 1<<N;
int mndist = 0xfffffff, mncity;
vector<int> rg[25];
for(i = 0; i < allstate; i++) {
if((i&must) != must)
continue;
int dist = 0, e = 0, node = 0;
vector<int> mst[25];
for(j = 0; j < N; j++) {
parent[j] = j;
node += (i>>j)&1;
}
e = node-1;
for(j = 0; j < N; j++) {
if(((i>>E[j].x)&1) && ((i>>E[j].y)&1)) {
x = findp(E[j].x);
y = findp(E[j].y);
if(x != y) {
dist += E[j].cost;
parent[x] = y;
e--;
mst[E[j].x].push_back(E[j].y);
mst[E[j].y].push_back(E[j].x);
}
}
}
if(e || dist > mndist || (dist == mndist && node > mncity))
continue;
if(mndist > dist || (mndist == dist && mncity > node)) {
mndist = dist, mncity = node;
for(j = 0; j < N; j++)
rg[j] = mst[j];
}
}
// mst -> rooted tree.
int visited[25] = {};
queue<int> Q;
Q.push(D), visited[D] = 1;
while(!Q.empty()) {
x = Q.front(), Q.pop();
for(i = 0; i < rg[x].size(); i++) {
if(visited[rg[x][i]] == 0) {
visited[rg[x][i]] = 1;
Q.push(rg[x][i]);
parent[rg[x][i]] = x;
}
}
}
printf("Case %d: distance = %d\n", ++cases, mndist);
for(i = 0; i < NJ; i++) {
printf(" %d", J[i]+1);
x = parent[J[i]];
while(x != D) {
printf("-%d", x+1);
x = parent[x];
}
printf("-%d\n", D+1);
}
puts("");
}
return 0;
}
文章定位：
