滴滴笔试毕业旅行——回溯法(dfs)

题目：

题目描述：
小滴正在筹划他的毕业旅行。他打算去找他的外国网友们，首先第一站是法国巴黎，但是去巴黎的路线有很多，交通工具也有很多可供选择。

现在有一个结点数为n，边的条数为m的无向图表示小滴到巴黎的所有路线。其中小滴的家为结点s，巴黎为结点e，小滴出发时间为start，请问小滴最早什么时候能到达巴黎？



输入描述
单组输入，数字间有空格隔开。

第一行两个整数：结点数n，边数m（n<=1000,m<=10000）。

第二行到第m+1行每行各有三个整数：结点u，结点v，需要的时间time（1<=u,v<=n，time<50，time以小时为单位）。

最后一行为家的位置：s，巴黎的位置：e，出发时间start（1<=s,e<=n，出发时间格式为month.day/hour，小时为24小时制，出发年份默认为2020年，且一定会在2020年到达，数据保证有解。）

输出描述
最早能到达巴黎的时间e time（格式与出发时间格式相同）。


样例输入
4 4
1 2 5
1 3 6
2 4 8
3 4 6
1 4 7.9/8
样例输出
7.9/20

提示
输入样例2
4 4
1 2 25
1 3 18
2 4 28
3 4 22
1 4 7.9/8

输出样例2
7.11/0

c++代码实现： 这里只求了最短时间，还没有换算成月/日/时的格式：

//回溯法-深度优先遍历
#include<iostream>
#include<vector>
#include<string>

using namespace std;


int dfs(vector<vector<int>>inputs, int i, int end, int count, int m, vector<bool>& visited)
{
          
   
	visited[i] = true;
	if (inputs[i][1] == end)
	{
          
   
		count += inputs[i][2];
		return count;
	}
	int min_count = 9999;
	int temp = count;
	for (int j = 0; j < m; j++)
	{
          
   
		if (inputs[j][0] == inputs[i][1] && visited[j] == false)
		{
          
   
			count += inputs[i][2];
			count =  dfs(inputs, j, end, count, m, visited);//重点
			min_count = min_count > count ? count : min_count;//重点
			visited[j] = false;
		}
		count = temp;//重点，注意把循环之前的count保留下来
	}
	return min_count;
}

int main()
{
          
   
	int n, m;
	cin >> n >> m;
	vector<vector<int>>inputs(m, vector<int>(3, 0));
	for (int i = 0; i < m; i++)
	{
          
   
		for (int j = 0; j < 3; j++)
		{
          
   
			cin >> inputs[i][j];
		}
	}
	int start;
	int end;
	string time;
	int min_count = 999999;
	cin >> start >> end >> time;
	vector<bool>visited(m, false);
	for (int i = 0; i < m; i++)
	{
          
   
		int count = 0;
		if (inputs[i][0] == start)
		{
          
   
			for (int i = 0; i < m; i++)
			{
          
   
				visited[i] = false;
			}
			count = dfs(inputs, i, end, count, m, visited);
			min_count = min_count < count ? min_count : count;
		}
	}
	cout << min_count << endl;
	return 0;
}