题目描述

Ken和Keiko分别住在Hakodate和Tokyo，他们需要在某个城市见面至少$30$分钟，且必须在$8:00$到$18:00$之间完成。他们可以选择任何城市作为见面地点，但必须确保在见面后能按时返回各自的城市。我们需要找到他们见面的最低总交通费用。

题意分析

输入： 火车连接信息，包括起点、终点、出发时间、到达时间和费用。

约束条件：

必须在$8:00$到$18:00$之间完成。 见面时间至少$30$分钟。 必须在$18:00$前返回各自的城市。

输出： 最低总交通费用，若无解则输出$0$。

解题思路

建模： 将城市和火车连接建模为图，其中节点是城市，边是火车连接，带有出发时间、到达时间和费用。

时间处理： 将时间转换为分钟数以便于计算。

最短路径： 使用Dijkstra算法计算从Hakodate和Tokyo到所有城市的最早到达时间和费用，同时考虑时间约束。

寻找见面点： 对于每个可能的见面城市，检查能否在该城市见面至少$30$分钟，并且能在$18:00$前返回各自的城市。计算总费用，并选择最小的总费用。

解决方法

数据结构：

Connection结构体存储火车连接的起点、终点、出发时间、到达时间和费用。 CityTime结构体用于优先队列，存储城市、到达时间和费用。

时间转换：

timeToMinutes将时间字符串转换为分钟数。 minutesToTime将分钟数转换为时间字符串。

Dijkstra算法： 计算从起点到所有城市的最早到达时间和最低费用。 使用优先队列优化，确保每次处理最早到达的节点。

主逻辑：

读取输入数据，构建图。 计算Ken和Keiko的最早到达时间和费用。 检查每个可能的见面城市，计算最低总费用。

C++代码实现：

#include<string>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
char in[20];
vector<pair<pair<int,int>,int> >g[110][1440];
vector<pair<pair<int,int>,int> >g2[110][1440];
int ijk[110][1440];
int v[110][1440];
int s[4][110][1440];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<110;i++)for(int j=0;j<1440;j++){
			g[i][j].clear();
			g2[i][j].clear();
		}
		map<string,int>m;
		m["Hakodate"]=0;
		m["Tokyo"]=1;
		int n=2;
		for(int i=0;i<a;i++){
			scanf("%s",in);
			string na=in;
			if(!m.count(na))m[na]=n++;
			int p=m[na];
			int H,M;
			scanf("%d:%d",&H,&M);
			int t1=H*60+M;
			scanf("%s",in);
			string nb=in;
			if(!m.count(nb))m[nb]=n++;
			int q=m[nb];
			scanf("%d:%d",&H,&M);
			int t2=H*60+M;
			int r;
			scanf("%d",&r);
			g[p][t1].push_back(make_pair(make_pair(q,t2),r));
			g2[q][t2].push_back(make_pair(make_pair(p,t1),r));
		}
		for(int i=0;i<110;i++)for(int j=0;j<1440;j++){
			v[i][j]=0;ijk[i][j]=99999999;
		}
		priority_queue<pair<int,pair<int,int> > > Q;
		Q.push(make_pair(0,make_pair(0,480)));
		ijk[0][480]=0;
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int t=Q.top().second.second;
			Q.pop();
			if(v[at][t])continue;
			v[at][t]=1;
			if(t<1080&&!v[at][t+1]&&ijk[at][t+1]>cost){
				ijk[at][t+1]=cost;
				Q.push(make_pair(-cost,make_pair(at,t+1)));
			}
			for(int i=0;i<g[at][t].size();i++){
				int x=g[at][t][i].first.first;
				int y=g[at][t][i].first.second;
				int z=g[at][t][i].second;
				if(!v[x][y]&&ijk[x][y]>cost+z){
					ijk[x][y]=cost+z;
					Q.push(make_pair(-cost-z,make_pair(x,y)));
				}
			}
		}
		for(int i=0;i<n;i++)for(int j=0;j<1440;j++)
			s[0][i][j]=ijk[i][j];
		for(int i=0;i<110;i++)for(int j=0;j<1440;j++){
			v[i][j]=0;ijk[i][j]=99999999;
		}
		Q.push(make_pair(0,make_pair(1,480)));
		ijk[1][480]=0;
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int t=Q.top().second.second;
			Q.pop();
			if(v[at][t])continue;
			v[at][t]=1;
			if(t<1080&&!v[at][t+1]&&ijk[at][t+1]>cost){
				ijk[at][t+1]=cost;
				Q.push(make_pair(-cost,make_pair(at,t+1)));
			}
			for(int i=0;i<g[at][t].size();i++){
				int x=g[at][t][i].first.first;
				int y=g[at][t][i].first.second;
				int z=g[at][t][i].second;
				if(!v[x][y]&&ijk[x][y]>cost+z){
					ijk[x][y]=cost+z;
					Q.push(make_pair(-cost-z,make_pair(x,y)));
				}
			}
		}
		for(int i=0;i<n;i++)for(int j=0;j<1440;j++)
			s[1][i][j]=ijk[i][j];
		for(int i=0;i<110;i++)for(int j=0;j<1440;j++){
			v[i][j]=0;ijk[i][j]=99999999;
		}
		Q.push(make_pair(0,make_pair(0,1080)));
		ijk[0][1080]=0;
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int t=Q.top().second.second;
			Q.pop();
			if(v[at][t])continue;
			v[at][t]=1;
			if(t>480&&!v[at][t-1]&&ijk[at][t-1]>cost){
				ijk[at][t-1]=cost;
				Q.push(make_pair(-cost,make_pair(at,t-1)));
			}
			for(int i=0;i<g2[at][t].size();i++){
				int x=g2[at][t][i].first.first;
				int y=g2[at][t][i].first.second;
				int z=g2[at][t][i].second;
				if(!v[x][y]&&ijk[x][y]>cost+z){
					ijk[x][y]=cost+z;
					Q.push(make_pair(-cost-z,make_pair(x,y)));
				}
			}
		}
		for(int i=0;i<n;i++)for(int j=0;j<1440;j++)
			s[2][i][j]=ijk[i][j];
		for(int i=0;i<110;i++)for(int j=0;j<1440;j++){
			v[i][j]=0;ijk[i][j]=99999999;
		}
		Q.push(make_pair(0,make_pair(1,1080)));
		ijk[1][1080]=0;
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int t=Q.top().second.second;
			Q.pop();
			if(v[at][t])continue;
			v[at][t]=1;
			if(t>480&&!v[at][t-1]&&ijk[at][t-1]>cost){
				ijk[at][t-1]=cost;
				Q.push(make_pair(-cost,make_pair(at,t-1)));
			}
			for(int i=0;i<g2[at][t].size();i++){
				int x=g2[at][t][i].first.first;
				int y=g2[at][t][i].first.second;
				int z=g2[at][t][i].second;
				if(!v[x][y]&&ijk[x][y]>cost+z){
					ijk[x][y]=cost+z;
					Q.push(make_pair(-cost-z,make_pair(x,y)));
				}
			}
		}
		for(int i=0;i<n;i++)for(int j=0;j<1440;j++)
			s[3][i][j]=ijk[i][j];
		int ret=999999999;
		for(int i=0;i<n;i++){
			for(int j=480;j<=1410;j++){
				ret=min(ret,s[0][i][j]+s[1][i][j]+s[2][i][j+30]+s[3][i][j+30]);
			}
		}
		if(ret>99999999)printf("0\n");
		else printf("%d\n",ret);
	}
}