首页 > 其他分享 >HDU-5418 Floyd + DP

HDU-5418 Floyd + DP

时间:2022-12-02 14:44:09浏览次数:69  
标签:HDU int scanf 5418 Floyd include dp

题目传送门

时间复杂度: \(O(2^n \cdot n^2)\)

注意:输入尽量用scanf输入, 输入需要记录两个路径的最小值

代码:

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <cstring>
#include <map>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 20;


int n, m;

int d[N][N], dp[20][1 << 17];

void init() {
	memset(d, 0x3f, sizeof d);
	for (int i = 1; i <= n; i ++) {
		dp[i][i] = 0;
	}
}

void floyd() {
	for (int k = 1; k <= n; k ++)  {
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}


int main() {
	int _;
	cin >> _;
	while (_ --) {
		cin >> n >> m;

		init();
		memset(dp, 0x3f, sizeof dp);

		for (int i = 0; i < m; i ++) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			if (d[a][b] != INF)
				d[a][b] = d[b][a] = min(d[b][a], c);
			else
				d[a][b] = d[b][a] = c;
		}

		if (n == 1) {
			cout << 0 << endl;
			continue;
		}

		floyd();

		for (int i = 1; i <= n; i ++) {
			dp[i][0] = d[i][1];
		}

		dp[1][1] = 0;

		for (int j = 1; j < 1 << n; j ++) {

			for (int k = 1; k <= n; k ++) {
				if (j & (1 << k - 1) == 0) continue;

				for (int i = 1; i <= n; i ++) {
					if (j & (1 << i - 1) == 1)  continue;	

					dp[i][j] = min(dp[i][j], d[i][k] + dp[k][j ^ (1 << k - 1)]);
				}		
			}
		}

		printf("%d\n", dp[1][(1 << n) - 2]);
	}
}

标签:HDU,int,scanf,5418,Floyd,include,dp
From: https://www.cnblogs.com/jacklee404/p/16944447.html

相关文章

  • HDU 6273 Master of GCD(差分)
    题目分析贴一个别人的题解这个题就是一个差分数组,因为这数列的最大公约数就是这个数列2的出现2的最少次数的幂乘以3的出现3的最少次数的幂将2和3分开讨论,然后分......
  • hdu最佳编码(哈夫曼编码)
    ProblemDescription文本编码是计算机通信中的常见问题。以文本“AAAAABCD”为例,如果使用ASCII,则一共需要64位(因为每个字符的ASCII编码都是需要8位)。对应的,如果我们将......
  • hdu棋盘游戏(二分图匹配)
    题目描述ProblemDescription小希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是Gardon限......
  • 经典算法——最短路径(Floyd+Dijkstra)
    Floyd时间复杂度:O(n^3)简介:作为最短路算法中复杂度最高的算法没有之一,标志性结构三层循环,核心结构本质DP思想具 有动态规划的无后效性他真的没有优点啦?!不,他有!虽然SPF......
  • hdu 5418 Victor and World
    hdu5418VictorandWorldTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:262144/131072K(Java/Others)链接:http://acm.hdu.edu.cn/showproblem.php?pi......
  • Floyd算法(最短路径)
    Floyd算法允许图中有带负权值的边,但不许有包含带负权值的边组成的回路。     上一篇文章我们通过迪杰斯特拉算法解决了从某个源点到其余各顶点的最短路径问题。从循......
  • HDU-1007 Quoit Design [平面最近点对]
    QuoitDesignTimeLimit:10000/5000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):86145    AcceptedSubmission(s):......
  • [边数限制最短路 倍增floyd 矩阵优化]Cow Relays G
    [边数限制最短路倍增floyd矩阵优化]CowRelaysG题目思路边数限制的最短路?bellman_ford可以拿来解决边数<=k的最短路,但这题是边数恰好为k,可以通过奇妙操作改成恰好经过k......
  • HDU:1091 的 python3 和 golang 实现
    python3defhdu_1091():whileTrue:s=input("input")s1=s.split("")ifs1[0]=="0"ands1[1]=="0":break......
  • HDU:1090 的 python3 和 golang 实现
    python3defhdu_1090():a=int(input(""))whilea!=0:s=input("input")s1=s.split("")print(int(s1[0])+int(s1[1]))......