A40221. 最优旅行
题目描述
最优旅行
题目描述
中国的高铁四通八达，乘坐方便，小明经常乘坐高铁在城市间旅游。
现在，小明又有了一个长假，他打算继续乘坐高铁旅游。这次，他打算到 下面的城市旅游。
上海、广州、长沙、西安、杭州、济南、成都、南京、昆明、郑州、天津、 太原、武汉、重庆、南昌、长春、沈阳、贵阳、福州。
小明打算从北京出发，游览以上每个城市正好一次，最终回到北京。在每 个城市（除北京外），小明都至少停留 24 小时。而当小明决定从一个城市去往 另一个城市时，他只会选择有直接高铁连接的城市，不会在中途换乘转车。
在试题目录下有一个文件 trip.txt 保存了小明可以选择的车次，小明不会 选择其他车次。 小明出发的时间是第 1 天的中午 12:00。
请问，小明游览完以上城市正好一 次，最终回到北京，最快需要多少分钟（请注意单位为分钟）
// trip.txt
车次 出发站 到达站 出发时间 到达时间
G169 北京 上海 16:40 22:35
G21 北京 上海 19:08 23:40
G18 上海 北京 17:55 22:36
G68 广州 北京 11:13 21:10
G67 北京 广州 12:13 22:19
G1305 上海 广州 15:25 23:38
G86 广州 上海 08:00 14:50
G6122 广州 长沙 21:00 23:36
G6117 长沙 广州 17:55 20:39
G502 长沙 北京 07:36 14:24
G503 北京 长沙 14:41 21:14
G1359 上海 长沙 15:37 20:59
G1348 长沙 上海 09:00 13:41
G362 西安 上海 08:49 14:45
G1936 上海 西安 16:12 22:54
G87 北京 西安 14:00 18:20
G88 西安 北京 13:30 17:55
G98 西安 广州 09:57 17:39
G836 广州 西安 11:24 20:09
G1404 广州 杭州 15:56 23:25
G20 杭州 北京 07:48 12:20
G39 北京 杭州 19:04 23:22
G7355 上海 杭州 21:30 22:28
G7558 杭州 上海 07:06 08:12
G300 济南 上海 06:50 11:40
G333 北京 济南 19:55 21:55
G336 济南 北京 07:45 09:33
G2056 广州 济南 08:05 18:34
G2058 济南 广州 10:14 20:49
G350 成都 北京 07:00 14:46
G89 北京 成都 06:53 14:38
G1888 成都 南京 11:28 22:00
G7180 上海 南京 10:05 11:29
G7003 南京 上海 08:00 09:39
G7613 南京 杭州 16:19 17:40
G7604 杭州 南京 12:09 13:30
G1540 昆明 南京 10:20 21:14
G1539 南京 昆明 09:05 19:40
G2883 成都 昆明 08:51 14:29
G2884 昆明 成都 12:16 17:57
G1538 昆明 郑州 08:46 18:48
G1537 郑州 昆明 10:38 20:49
G2001 郑州 西安 07:52 10:24
G2002 西安 郑州 08:10 10:29
G2231 西安 重庆 17:06 22:56
G2232 重庆 西安 07:05 12:37
G8594 重庆 成都 06:50 08:07
G8599 成都 重庆 22:12 23:29
G1709 天津 重庆 08:05 19:39
G1710 重庆 天津 10:49 22:45
G8901 北京 天津 22:10 22:45
G8928 天津 北京 19:08 19:46
G2609 天津 太原 10:40 14:15
G2610 太原 天津 14:43 18:12
G1954 太原 上海 12:26 21:17
G1952 上海 太原 08:10 17:28
G686 郑州 太原 13:17 17:16
G688 太原 郑州 17:38 21:38
G1864 太原 杭州 12:50 21:10
G1862 杭州 太原 07:14 15:50
G91 北京 太原 08:40 11:07
G92 太原 北京 08:33 11:00
G694 太原 武汉 16:37 22:29
G692 武汉 太原 09:48 16:00
G1722 武汉 上海 08:00 11:53
G1720 上海 武汉 13:51 17:50
G858 西安 武汉 15:18 19:48
G856 武汉 西安 09:17 14:27
G365 天津 武汉 14:56 20:41
G366 武汉 天津 14:30 20:32
G294 长沙 天津 08:47 16:56
G292 天津 长沙 10:58 18:50
G696 长沙 太原 09:23 17:55
G698 太原 长沙 10:46 18:18
G1391 杭州 昆明 11:43 22:53
G1392 昆明 杭州 09:06 20:18
G1514 昆明 南昌 16:00 22:54
G1511 南昌 昆明 08:25 15:38
G1462 南昌 杭州 12:24 15:28
G1451 杭州 南昌 12:30 15:26
G1244 济南 长春 07:42 15:07
G1242 长春 济南 15:33 22:35
G8033 沈阳 长春 06:42 08:40
G1290 长沙 长春 07:21 21:09
G1292 长春 长沙 08:47 22:08
G400 长春 北京 08:32 14:48
G399 北京 长春 15:20 21:45
G1886 南京 成都 08:07 17:54
G579 南京 长沙 09:27 14:10
G580 长沙 南京 15:53 20:40
G1484 贵阳 南京 07:58 18:02
G2335 南京 贵阳 12:07 21:58
G2105 长沙 贵阳 13:17 16:55
G2116 贵阳 长沙 08:11 11:26
G2201 郑州 成都 07:10 13:19
G2212 成都 郑州 16:57 23:04
G1814 上海 郑州 14:15 18:12
G370 郑州 上海 07:33 12:02
G1274 武汉 沈阳 07:23 19:03
G1272 沈阳 武汉 07:32 19:20
G2869 重庆 昆明 07:43 11:55
G2870 昆明 重庆 14:52 19:09
G1335 重庆 上海 08:48 20:56
G1333 上海 重庆 11:39 23:29
G1759 南昌 重庆 07:08 14:45
G1761 重庆 南昌 15:12 22:23
G1493 南京 南昌 13:00 17:21
G1496 南昌 南京 09:04 13:25
G5314 南昌 福州 08:13 11:09
G5312 福州 南昌 18:30 21:25
G1256 长春 上海 11:53 22:54
G1258 上海 长春 09:08 20:05
G1284 沈阳 成都 07:02 21:47
G1282 成都 沈阳 09:06 23:13
G217 北京 沈阳 13:30 17:15
G218 沈阳 北京 08:11 11:58
G2604 沈阳 太原 15:34 23:00
G2602 太原 沈阳 07:44 15:14
G8664 贵阳 成都 19:15 22:35
G8691 成都 贵阳 11:11 14:31
G2958 贵阳 广州 14:03 20:26
G2960 广州 贵阳 07:27 13:43
G1521 武汉 贵阳 08:01 13:25
G1524 贵阳 武汉 14:23 19:33
G1609 福州 广州 08:16 14:15
G1607 广州 福州 14:55 21:05
G1696 昆明 福州 11:11 22:02
G1698 福州 昆明 08:41 19:28
G1636 福州 上海 12:26 16:55
G1631 上海 福州 07:54 12:15
G1642 福州 杭州 14:45 18:32
G1641 杭州 福州 18:55 22:38
参考答案
#include <bits/stdc++.h>
using namespace std;
/*
将城市转化数字，从而转化为图论结构
北京--1 上海--2 广州--3 长沙--4 西安--5 杭州--6
济南--7 成都--8 南京--9 昆明--10 郑州--11 天津--12
太原--13 武汉--14 重庆--15 南昌--16 长春--17 沈阳--18
贵阳--19 福州--20
*/
struct Node {
int e; //终点
int starttime, endtime; //起始时间，到达时间(转换为分钟表示)
int cost; // 运行时间
Node(int des, int startt, int endt, int time): e(des), starttime(startt), endtime(endt), cost(time) {}
Node() {}
};
vector<vector<Node> > G(25); //存放所有班次信息
map<string, int> m;
long long mintime = 0x3f3f3f3f3f3f3f;
long long totaltime = 0;
int vis[25]; //标志去过哪些城市了(每个城市只能去一次，除了北京）
void INIT() {
m.insert(make_pair("北京", 1));
m.insert(make_pair("上海", 2));
m.insert(make_pair("广州", 3));
m.insert(make_pair("长沙", 4));
m.insert(make_pair("西安", 5));
m.insert(make_pair("杭州", 6));
m.insert(make_pair("济南", 7));
m.insert(make_pair("成都", 8));
m.insert(make_pair("南京", 9));
m.insert(make_pair("昆明", 10));
m.insert(make_pair("郑州", 11));
m.insert(make_pair("天津", 12));
m.insert(make_pair("太原", 13));
m.insert(make_pair("武汉", 14));
m.insert(make_pair("重庆", 15));
m.insert(make_pair("南昌", 16));
m.insert(make_pair("长春", 17));
m.insert(make_pair("沈阳", 18));
m.insert(make_pair("贵阳", 19));
m.insert(make_pair("福州", 20));
memset(vis, 0, sizeof(vis));
}
void dfs(int s, int endt, int len) { //s为起点城市，endt为到达此城市的时间，len为当前旅游过哪些城市了
if (s == 1 && len > 0) { //到达北京就要回溯 (除了开始从北京出发)
bool flag = true;
for (int i = 1; i <= 20; i++) //检查是否旅游完毕
if (vis[i] == 0)
flag = false;
vis[1] = 0; //北京始终允许反复访问（在北京多次中转）
if (flag) //走遍所有地点（19个旅游城市+1个终点城市北京）
mintime = min(mintime, totaltime);
/*
注：如果直接if(len==20)判断的话，会忽略掉可以经过北京中转的情况，
虽然此题结果经过北京中转不会使时间减少，但是我们设计程序应该考虑全面
*/
return;
}
for (int i = 0; i < G[s].size(); i++) {
Node r = G[s][i];
if (vis[r.e] == 0) { //目的城市没去过
vis[r.e] = 1;
long long temp = totaltime;
//time1: 此班车的运行时间
totaltime += r.cost;
//time2: 班次间隔时间(24h内)
if (s != 1 && r.starttime > endt) //此班车出发时间和上一班结束时间的关系
totaltime += r.starttime - endt; //休息时间（当日）
if (s != 1 && r.starttime < endt)
totaltime += r.starttime - endt + 1440; //跨日
//time3: 从北京出发时的等车时间
if (s == 1) {
if (r.starttime > 720) //十二点出发
totaltime += r.starttime - 720;
else
totaltime -= r.starttime - 720 + 1440; //只有等到明天才能出发了
}
//最优性剪枝:不剪枝会花跑很久
if (totaltime > mintime) {
totaltime = temp;
continue;
}
dfs(r.e, r.endtime, len + 1);
vis[r.e] = 0;
totaltime = temp;
}
}
}
int main() {
INIT();
//freopen("trip.txt","r",stdin); //注意：从文件中读取文字信息会发生乱码
//读入某行信息也可以使用getline(cin,str);
string str;
for (int i = 1; i <= 5; i++) //读入第一行无用数据
cin >> str;
for (int i = 1; i <= 132; i++) { //共有132班车
cin >> str; //去掉无用的班次名字
string src, des; //起始站-->终点站
string s, t; //出发时间-->到达时间
cin >> src >> des >> s >> t;
//换算时间为分钟表示
int a, b;
a = (s[0] - '0') * 600 + (s[1] - '0') * 60 + (s[3] - '0') * 10 + (s[4] - '0');
b = (t[0] - '0') * 600 + (t[1] - '0') * 60 + (t[3] - '0') * 10 + (t[4] - '0');
int cost; //运行时间
if (a < b)
cost = b - a;
else
cost = b - a + 1440; //+1天
//存入图中
G[m[src]].push_back(Node(m[des], a, b, cost));
}
//检验所有班次以及城市信息的录入情况
//for(int i=0;i<25;i++)
// for(int j=0;j<G[i].size();j++)
// {
// Node r=G[i][j];
// cout<<i<<" "<<r.e<<" "<<r.starttime<<" "<<r.endtime<<" "<<r.cost<<endl;
// }
dfs(1, 0, 0); //从北京出发
mintime += 1440 * 19; //加上19天的停留(如果经过北京中转，不会停留24h)
/*任意两趟班次之间：前一班的到达时间 到 下一班的发车时间间隔都是小于24h
例如：前一班15:30到，下一班16.30出发 需要休息一天+24h
前一班15.30到，下一班08.30出发 也需要休息一天+24h
*/
cout << mintime;
return 0;
}
//注意：班次信息为每天固定发车，即每天都会同一时间发同一班车
//ANS : 47373答案解析
答案：47373 (个人答案)