Floyd多源最短路板子

注意事项

1.Floyd限制条件少，负权值，非连通图，有向图都可以使用Floyd

2.Floyd复杂度很高

3.该模板可解决一条边重复输入，原地TP（s和t相同）带来的问题

题目

输入：

测试组数t

节点个数n

节点间关系数m

m组关系 每组包括

端点u 端点v 边的权值w

查询数q

q组查询 每组包括

端点s 端点t

输出：

q组查询结果 每组包括

d代表端点s到端点t的的最小权值和

题解

数据结构：

用邻接矩阵R存储，初始化所有关系权值为无穷大

算法：

对每个节点进行松弛操作

复杂度O（n^3）

代码实现：

// label:
// open this to ban assert() after debug
// #define NDEBUG
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
#define heap priority_queue
#define pll pair
#define str string
#define fir first
#define sec second
#define SPO(n) fixed << setprecision(n)
#define FOR(i, l, r) for (long long(i) = (l); (i) <= (r); ++(i))
#define ROF(i, r, l) for (long long(i) = (r); (i) >= (l); --(i))
#define endl 'n'
#ifdef debugcmd
#define DBG(n) cout << "!!! " << #n << ": " << n << 'n'
#else
#define DBG(n) ;
#endif
// const double PI = acos(-1.0);
const int IINF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1.0e-9;
const long long MOD = 1e9 + 7;
const long long MAX = 1e3 + 5;
ll n;
ll r[MAX][MAX];

void Floyd(void)
{
	FOR(k, 1, n)
	FOR(i, 1, n)
	FOR(j, 1, n)
	r[i][j] = min(r[i][j], (r[i][k] + r[k][j]));
	return;
}
void Solve(void)
{
	cin >> n;
	memset(r, IINF, sizeof(r));
	FOR(i, 1, n)
	r[i][i] = 0;
	ll m;
	cin >> m;
	while (m--)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		r[u][v] = min(r[u][v], w);
		r[v][u] = min(r[v][u], w);
	}
	Floyd();
	ll q;
	cin >> q;
	while (q--)
	{
		ll s, t;
		cin >> s >> t;
		cout << r[s][t] << endl;
	}
	return;
}
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	// #ifdef cincoutcmd
	// freopen("cin.txt","r",stdin);
	// freopen("cout.txt","w",stdout);
	// #endif
	ll t;
	cin>>t;
	while(t--)
	Solve();
	return 0;
}