#include
#include
using?namespace?std;
#define?Maxn?500
class?graph{
public:
????mapid;
????string?place[Maxn];
????int?tot=0;
????struct?point{
????????int?numdis;
????????int?nowtime;
????????bool?operator<（const?point?&b）const{
????????return?this->dis????????bool?operator>（const?point?&b）const{
????????return?this->dis>b.dis;}
????};
????struct?line{
????????string?BeginEnd;
????????string?number;
????????int?sted;
????????int?begintimeendtime;
????????int?disprice;
????????int?change（string?s）
????????{
????????????int?res=（（s[0]-‘0‘）*10+（s[1]-‘0‘））*60;
????????????res+=（（s[3]-‘0‘）*10+（s[4]-‘0‘））;
????????????return?res;
????????}
????????line（）
????????{
????????????Begin=““;End=““;number=““;
????????????st=ed=begintime=endtime=price=0;
????????}
????????line（string?numstring?astring?bstring?cstring?dint?sint?tint?p）
????????{
????????????number=num;Begin=a;End=b;
????????????begintime=change（c）;endtime=change（d）;
????????????st=s;ed=t;
????????????price=p;
????????}
????????void?showtime（int?t）
????????{
????????????printf（“%02d:%02d“t/60t%60）;
????????}
????????void?print（）
????????{
????????????cout<????????????showtime（begintime）;cout<<“?“;showtime（endtime）;cout<<“?“;
????????????cout<????????}
????};//邊的各種信息，構造函數
????vectorair[Maxn];
????vectortrain[Maxn];
????graph（）
????{
????????tot=0;
????????id.clear（）;
????????for（int?i=0;i????????for（int?i=0;i????}//初始化
????int?passtime（int?xint?ybool?f）
????{
????????if（f）return?0;
????????x=x%1440;
????????y=y%1440;
????????return?（y-x+1440）%1440;
????}
????int?length（line?kint?typepoint?intempint?stint?dis）
????{
????????if（type==1）//求時間最短
????????{
????????????return?passtime（k.begintimek.endtime0）+passtime（disk.begintimest==intemp.num）;
????????}
????????if（type==2）//求花費最短
????????{
????????????return?k.price;
????????}
????????if（type==3）//求中轉最短
????????{
????????????return?1;
????????}
????}
????void?printpath（int?stint?vline?path[]）
????{
????????if（v==st）return?;
????????printpath（stpath[v].stpath）;
????????path[v].print（）;
????}//打印路徑
????void?showshow（int?Time）
????{
????????int?h=Time/60m=Time%60;
????????printf（“%d小時%d分“hm）;
????}//修改時間格式
????void?shortpath（int?stint?edvector?edge[]int?type）
????{
????????bool?mark[Maxn];
????????int?dis[Maxn];
????????line?path[Maxn];
????????const?int?inf=2000000;
????????int?iv;
????????point?intemp{st00}newtemp;
????????for（i=1;i<=tot;i++）
????????{
????????????mark[i]=false;
????????????dis[i]=inf;
????????}
????????dis[st]=0;
????????priority_queuegreater?>Q;
????????Q.push（intemp）;
????????mark[st]=true;
????????while（!Q.empty（））
????????{
????????????intemp=Q.top（）;
????????????Q.pop（）;
??????????