HDU 6797 Tokitsukaze and Rescue

数据量不大，暴力枚举删去的边
要删去的边一定是在最短路的路径里的， 所以进行 dij 后 dfs 删去的边

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int inf = 0x3f3f3f3f;

int T, n, k, x, y, z, ans;
int path[100], w[100][100], d[100];
bool visited[100], des[100][100];  //destory 

void dijkstra()
{
	memset(path, 0, sizeof path);
	memset(d, inf, sizeof d);
	memset(visited, false, sizeof visited);
	d[1] = 0;
	for(int i = 0; i < n-1; i++)
	{
		int minn = inf, f = 0;
		for(int j = 1; j <= n; j++) 
			if(!visited[j] && minn > d[j]) 
				minn = d[j], f = j;
		visited[f] = true;
		for(int j = 1; j <= n; j++)
		{
			if(!des[f][j] && d[j] > d[f]+w[f][j])
			{
				d[j] = d[f]+w[f][j];
				path[j] = f;
			}
		}
	}
}

void dfs(int x)
{
	dijkstra();
	if(x == k+1)
	{
		ans = max(ans, d[n]);
		return;
	}
	for(int i = n, pre = n; i != 0; i = path[i])
	{
		des[pre][i] = des[i][pre] = true;
		dfs(x+1);
		des[pre][i] = des[i][pre] = false;
		pre = i; 
	}	
}

int main()
{
	scanf("%d", &T);
	while(T--)
	{
		memset(des, false, sizeof des);
		memset(w, inf, sizeof w);
		ans = 0;
		scanf("%d %d", &n, &k);
		for(int i = 1; i <= n; i++) w[i][i] = 0;
		for(int i = 0; i < n*(n-1)/2; i++)
		{
			scanf("%d %d %d", &x, &y, &z);
			w[x][y] = w[y][x] = z;
		}
		dfs(1);
		printf("%d\n", ans);
	}
	return 0;
 }

HDU 6797 Tokitsukaze and Rescue

原文：https://www.cnblogs.com/hucorz/p/14366995.html