POJ3613 Cow Relays（矩阵乘法floyd+快速幂）

超、凢脫俗 2021-11-16 08:34 263阅读 0赞

## 题意：给出一张无向连通图，求S到E经过k条边的最短路。 ##

## 分析：居然和矩阵快速幂联系起来了，详见《算法竞赛进阶指南》P363。 ##

## 代码： ##

#include <map>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 206, INF = 0x3f3f3f3f;
    int n, t, s, e, tot = 200;
    map<int, int> m;
    struct M {
    	int a[N][N];
    	void pre() {
    		for (int i = 1; i <= tot; i++)
    			for (int j = 1; j <= tot; j++)
    				a[i][j] = INF;
    	}
    } st, ed;
    
    M mul(M a, M b) {
    	M c;
    	c.pre();
    	for (int i = 1; i <= tot; i++)
    		for (int j = 1; j <= tot; j++)
    			for (int k = 1; k <= tot; k++)
    				c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);
    	return c;
    }
    
    int main() {
    	cin >> n >> t >> s >> e;
    	st.pre();
    	tot = 0;
    	while (t--) {
    		int x, y, z;
    		scanf("%d %d %d", &z, &x, &y);
    		x = m[x] ? m[x] : (m[x] = ++tot);
    		y = m[y] ? m[y] : (m[y] = ++tot);
    		st.a[x][y] = st.a[y][x] = z;
    	}
    	memcpy(ed.a, st.a, sizeof(ed.a));
    	--n;
    	while (n) {
    		if (n & 1) ed = mul(ed, st);
    		st = mul(st, st);
    		n >>= 1;
    	}
    	cout << ed.a[m[s]][m[e]] << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，263人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj3233(矩阵快速幂)

Matrix Power Series <table> <tbody> <tr> <td><strong>Time Limit:</strong>&nbsp

雨点打透心脏的1/2处/ 2024年02月17日 19:21/ 0 赞/ 38 阅读

相关 poj3070 矩阵快速幂

Fibonacci <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

古城微笑少年丶/ 2024年02月17日 19:21/ 0 赞/ 38 阅读

相关 poj 3070 Fibonacci 矩阵快速幂

include <cstdio> include <cstring> using namespace std; define M_H

谁借莪１个温暖的怀抱￠/ 2022年08月08日 05:21/ 0 赞/ 174 阅读

相关 poj 3070 矩阵快速幂

poj3070 include <cstdio> include <cstring> using namespace std;

￡神魔★判官ぃ/ 2022年08月07日 14:53/ 0 赞/ 135 阅读

相关 poj 3660 Cow Contest【floyd】

Cow Contest <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

落日映苍穹つ/ 2022年08月04日 13:49/ 0 赞/ 163 阅读

相关 poj3613-floyd+邻接矩阵乘法

参考于：08年论文：俞华程《矩阵乘法在信息学中的应用》图邻接矩阵上的乘法：图的邻接矩阵可以唯一地表示一张图，并且有很多神奇的性质。接

小灰灰/ 2022年07月12日 04:51/ 0 赞/ 160 阅读

相关 poj-3734(矩阵快速幂+推导)

问题描述: Panda has received an assignment of painting a line of blocks. Since Panda is suc

妖狐艹你老母/ 2022年06月09日 04:26/ 0 赞/ 211 阅读

相关 poj Fibonacci 矩阵快速幂

题目链接：[点我][Link 1] Description In the Fibonacci integer sequence, F0 = 0, F1 = 1, and

向右看齐/ 2022年05月16日 11:22/ 0 赞/ 181 阅读

相关 POJ3613 Cow Relays（矩阵乘法floyd+快速幂）

题意：给出一张无向连通图，求S到E经过k条边的最短路。分析：居然和矩阵快速幂联系起来了，详见《算法竞赛进阶指南》P363。代码： include

超、凢脫俗/ 2021年11月16日 08:34/ 0 赞/ 264 阅读

相关 POJ3070Fibonacci（矩阵快速幂）

在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1) 。给定整数n，求Fibnmod10000 。输入格式输入包含多组

小咪咪/ 2021年10月25日 12:22/ 0 赞/ 329 阅读