CodeForces Gym 100646H You’ll be Working on the Railroad DFS

就是给你一个图，保证0号点和1号点是连通的，让你求一个简单最短路径，但是最短路是这样定义的

假如只经过了一条边，路径长度就是这条边的长度

假如经过了两条边，路径长度就是这两个的最小值

假如经过了>=3条边，路径长度就是所有边的和，再减去所有边中最大的那两个

然后，可以DP去做，先预处理出边数<=2的方案，然后DP去做边数>=3的方案，

或者，直接DFS就行，44KB，31MS，快的飞起

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define ll long long
#define mod 1000000009
#define maxn 105
#define maxm 10003
#define INF 0x3f3f3f3f
int graph[maxn][maxn];
int N, M;
bool vis[maxn];
int anspath[maxn], len = 0;
int tmppath[maxn];
vector<int> value;
int sum;
void DFS(int s, int cnt)
{
	tmppath[cnt] = s;
	vis[s] = true;
	if (s == 1)
	{
		if (cnt == 1)
		{
			if ((graph[0][1] < sum) || (graph[0][1] == sum&&cnt + 1 < len))
			{
				sum = graph[0][1];
				anspath[0] = 0; anspath[1] = 1;
				len = 2;
			}
		}
		else if (cnt == 2)
		{
			int x = min(graph[0][tmppath[1]], graph[tmppath[1]][1]);
			if ((x < sum) || (x == sum&&cnt + 1 < len))
			{
				sum = x; len = 3;
				for (int i = 0; i < 3; ++i)
					anspath[i] = tmppath[i];
			}
		}
		else
		{
			int x = 0;
			value.clear();
			for (int i = 0; i < cnt; ++i)
				value.push_back(graph[tmppath[i]][tmppath[i + 1]]);
			sort(value.begin(), value.end());
			for (int i = 0; i < value.size() - 2; ++i)
				x += value[i];
			if ((x < sum) || (x == sum&&cnt + 1 < len))
			{
				sum = x; len = cnt + 1;
				for (int i = 0; i <= cnt; ++i)
					anspath[i] = tmppath[i];
			}
		}
		vis[s] = false;
		return;
	}
	for (int i = 0; i < N; ++i)
	{
		if (graph[s][i]>0 && !vis[i])
		{
			DFS(i, cnt + 1);
		}
	}
	vis[s] = false;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	while (scanf("%d", &M) != EOF)
	{
		if (M == 0)
			break;
		N = 0; sum = INF; len = 0;
		memset(graph, 0, sizeof(int)*maxn*maxn);
		int s, e, c;
		for (int i = 0; i < M; ++i)
		{
			scanf("%d%d%d", &s, &e, &c);
			graph[s][e] = c; graph[e][s] = c;
			if (s > N)
				N = s;
			if (e > N)
				N = e;
		}
		++N;
		memset(vis, 0, sizeof(vis));
		DFS(0, 0);
		for (int i = 0; i < len; ++i)
			printf("%d ", anspath[i]);
		printf("%d\n", sum);
	}
	//system("pause");
	//while (1);
	return 0;
}