试题 算法训练 The Traveling Judges Problem
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
一组人要担任在一个特定城市举办的比赛的评委，他们需要找到最便宜的租车方式使得每个人都到达目标城市。他们观察发现，如果几个人在旅途的某一段坐同一辆租的车，就可以减少总费用。你的任务就是找出这些人应该采取的路线使得租车的总费用最小。
我们假定：
1. 租一辆车的费用与它行驶的距离成正比，没有燃油、保险、乘客人数多于一个等产生的额外费用。
2. 所有车的费用与行驶距离的比例相同。
3. 一辆车可以容纳任意数量的乘客。
4. 任意一对城市之间最多只有一条道路直接相连，每条道路都是双向的且长度大于0。
5. 每个人的起始城市到目标城市都至少有一种路线。
6. 若多个人的路线中经过同一城市，则这些人从该城市到目标城市必乘同一辆车。
7. 一个人可以乘一辆车到某个城市，再乘另一辆车离开该城市。
输入格式
第一行包含三个整数nc, dc和nr，表示地图上的城市个数，目标城市的编号和地图上的道路条数。
接下来nr行每行包含三个整数c1, c2和dist，表示一条长度为dist的双向道路(c1, c2)。
接下来一行包含一个整数nj，表示人数。
接下来一行包含nj个整数，表示每个人的起始城市。
输出格式
第一行包含“distance = ”和一个整数，表示所租的车行驶的最小总距离。
接下来nj行每行包含一个人的访问路线，城市按访问顺序给出并用“-”连接。
存在多种方案时，选择需要访问到的城市集合元素最少的一种；仍然存在多种方案时，选择集合元素升序排列后字典序最小的一种。
样例输入
5 3 5
1 2 1
2 3 2
3 4 3
4 5 1
2 4 2
2
5 1
样例输出
distance = 6
5-4-2-3
1-2-3
样例输入
4 4 3
1 3 1
2 3 2
3 4 2
2
1 2
样例输出
distance = 5
1-3-4
2-3-4
样例输入
3 3 3
1 2 2
1 3 3
2 3 1
2
2 1
样例输出
distance = 3
2-3
1-2-3
数据规模和约定
对于30%的数据，1 <= nc <= 8。
对于100%的数据，1 <= nc <= 20，1 <= nj <= 10，1 <= dist <= 100。
解题思路：先用Prim 算法（当所有起始城市都被访问过时 退出while循环），得出最小生成树。然后，遍历每个起始城市，不断向前回溯，访问其父节点，得到每段路径，若该路径未被访问（数组Cvis[i][j] 记录 城市i 与城市j 之间的道路 是否被访问），则加到res中；否则，跳过。 遍历结束后的res 即为 最终的distance。找每个起始城市到达dc的路径也是 向前回溯。代码只跑了40分，可能是 “存在多种方案时，选择需要访问到的城市集合元素最少的一种；仍然存在多种方案时，选择集合元素升序排列后字典序最小的一种。” 没处理好的问题。。。未完待续。。。
代码如下：
#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
#define MAXNC 22
struct Way{
int c1,c2;
int dist;
Way(){ }
Way(int cc1,int cc2,int dd):c1(cc1),c2(cc2),dist(dd){ }
bool operator <(const Way &W) const {
return dist>W.dist;
}
};
int father[MAXNC];
int vis[MAXNC];
int isSC[12];
int Cvis[MAXNC][MAXNC];// Gvis[i][j] 记录 城市i 与城市j 之间的道路 是否被访问，
vector<int> SC;
priority_queue<Way> PQ;
vector< Way> G[MAXNC];
int nc, dc,nr; //表示地图上的城市个数，目标城市的编号和地图上的道路条数。
int nj;
bool isAllReached(){
bool isAll=true;
for(int i=0;i<SC.size();i++){
int sc=SC[i];
if(vis[sc]==0){
isAll=false;
break;
}
}
return isAll;
}
void ReadInput(){
cin>>nc>>dc>>nr;
int c1,c2,dist;
for(int i=1;i<=nr;i++){
cin>>c1>>c2>>dist;
G[c1].push_back(Way(c1,c2,dist));
G[c2].push_back(Way(c2,c1,dist));
}
memset(isSC,0,sizeof(isSC));
memset(vis,0,sizeof(vis));
cin>>nj;
for(int i=0;i<nj;i++){
int sc;
cin>>sc;
isSC[sc]=1;
SC.push_back(sc);
}
for(int i=1;i<=nc;i++)
father[i]=i;
}
void Prim(int S){
// long long res=0;
vis[S]=1;
for(int i=0;i<G[S].size();i++){
int to=G[S][i].c2;
father[to]=S;
PQ.push(G[S][i]);
}
while(!PQ.empty()){
Way W=PQ.top();
PQ.pop();
if(vis[W.c2])
continue;
vis[W.c2]=1;
// res+=W.dist;
father[W.c2]=W.c1;
for(int i=0;i<G[W.c2].size();i++)
PQ.push(G[W.c2][i]);
if( isAllReached() )
break;
}
}
int findDist(int c1,int c2){
for(int i=0;i<G[c1].size();i++){
int to=G[c1][i].c2;
if(to==c2){
return G[c1][i].dist;
}
}
}
long long getTotalDist(){
memset(Cvis,0,sizeof(Cvis));
long long res=0;
for(int i=0;i<SC.size();i++){
int pos=SC[i];
while(1){
if( Cvis[pos][father[pos]]==0 ){
res+=findDist(pos,father[pos]);
Cvis[pos][father[pos]]=Cvis[ father[pos] ][ pos ]=1;
}
pos=father[pos];
if(father[pos]==pos)
break;
}
}
return res;
}
int main(int argc, char** argv) {
ReadInput();
cout<<"distance = ";
if(nj==1){
cout<<"0"<<endl;
cout<<SC[0]<<endl;
}
else{
Prim(dc);
cout<<getTotalDist()<<endl;
for(int i=0;i<SC.size();i++){
int pos=SC[i];
cout<<pos<<"-";
while(1){
pos=father[pos];
cout<<pos;
if(father[pos]==pos)
break;
cout<<"-";
}
cout<<endl;
}
}
return 0;
}