题解 | #两次广搜#

第一次广搜从终点站倒着往起点搜，这一次是判断搭乘某车能不能到终点站，用Node里的j标记 随后正着广搜，那么什么时候将边加入呢？当这个边的终点站能到终点并且有换乘选择的时候加入。 这里我筛了两次，第一次不管换乘，但是记录时间到一个set里，并且把边储存到另一个数组里，第二次跟最大值比较等于的话就不能加入了

#include <bits/stdc++.h>

using namespace std;

struct Node {int start,end,cost,time1,time2;bool j;};

struct re {struct Node node;int money;};

vector tu[501][501];

int time_tiqu(string k) { int i = 0; int time1 = 0; while(k[i] != ':') { time1 *= 10; time1 += k[i] - '0'; i++;

} time1 *= 60; int time2 = 0;i++; while(i < k.size()) { time2 *= 10; time2 += k[i] - '0'; i++; } return time1 + time2;

} bool cmp(const Node &a,const Node &b) { if(a.time1 != b.time1) return a.time1 < b.time1;

else
    return a.cost < b.cost;

} int main()

{
int n,m;cin >> n >> m;
int x,y,c;
string xx,yy;
queue <struct Node> p;
int mark = 0;
for(int i = 0;i < m;i++)
{
    cin >> x >> y >> c >> xx >> yy;
    int ts_1 = time_tiqu(xx),td_1 = time_tiqu(yy);
    /*cout << ts_1 << " " << td_1 << endl;*/
    tu[x][y].push_back({x,y,c,ts_1,td_1,false});

}
 tu[0][1].push_back({0,1,0,-30,-30,false});
for(int i = 1;i <= n;i++)
{
    for(int j = 1;j <= n;j++)
    {
        sort(tu[i][j].begin(),tu[i][j].end(),cmp);
    }
}
for(int i = 1;i <= n;i++)
{
    for(int j = 0;j < tu[i][n].size();j++)
    {
    tu[i][n][j].j = true;
	p.push(tu[i][n][j]);	
	
	}
   
}
while (!p.empty())
{
    
    struct Node temp = p.front();p.pop();
    for(int i = 1;i<= n;i++)
    {
        for(int j = 0;j <tu[i][temp.start].size();j++)
        {
            if(tu[i][temp.start][j].time2 + 30 <= temp.time1)
            {
                if(!tu[i][temp.start][j].j)
                {
                    tu[i][temp.start][j].j = true;
                    p.push(tu[i][temp.start][j]);
                    
                }
            }
        }
    }
   
}

queue q;

q.push({tu[0][1][0],0});
int result = INT_MAX - 1;
 while (!q.empty())
{

    struct re temp = q.front();q.pop();
       if(temp.node.end == n)
                {
                    result = min(result,temp.money);
                   
                }
    vector<struct Node> mid;
    set<int> t_mark;
    int mark = 0;
    for(int i = 1;i <= n;i++)
    {
			for(int j = 0;j < tu[temp.node.end][i].size();j++)
			{
				if((tu[temp.node.end][i][j].j) && (temp.node.time2 + 30 <= tu[temp.node.end][i][j].time1))
				{
					mid.push_back(tu[temp.node.end][i][j]);
					t_mark.insert(tu[temp.node.end][i][j].time1); 
				}
			}
		            
    }
    for(int i = 0;i < mid.size();i++)
    {
    	if(mid[i].time1 < (*t_mark.rbegin()))
    	{
    		q.push({mid[i],mid[i].cost + temp.money});
    		
		}
	}
    
    
     
}
if(result != INT_MAX - 1)
{cout << result;}
else
{cout << -1;}
return 0;

}