如何给公司做网站,网站建设板块建议,北京网站系统开发,外国网站在内地做seo原题链接#xff1a;
跑路 - 洛谷 解题思路#xff1a;
如果u到v之间有一条长度为2^t的路径#xff0c;那就把dis[u][v]改为1#xff0c;所以我们先结合倍增法跑一遍floyd#xff0c;得到新图#xff0c;然后在新图上再跑一次最短路#xff0c;这次可以用任何的最短路…原题链接
跑路 - 洛谷 解题思路
如果u到v之间有一条长度为2^t的路径那就把dis[u][v]改为1所以我们先结合倍增法跑一遍floyd得到新图然后在新图上再跑一次最短路这次可以用任何的最短路算法但我们还是选择最简单最好写的floyd。 代码CPP
#include bits/stdc.h
using namespace std;
#define endl \n
typedef long long ll;
typedef unsigned long long ull;
const int maxn 55;
const int INF 0x3fffffff;
const int mod 1000000007;
bool p[maxn][maxn][maxn]; // p[u][v][t] true表示u、v之间有一条长度为2^t的路径
int dis[maxn][maxn];void solve() {fill(dis[0], dis[0] maxn * maxn, INF);int n, m;cin n m;for (int i 1; i m; i) {int u, v;cin u v;dis[u][v] 1;p[u][v][0] true;}// 利用倍增原理计算新图。根据floyd的思路路径通过一个中转点k有p[i][j][t] p[j][k][t - 1] p[k][j][t - 1]for (int t 1; t 32; t) { // 长度为2^t的路径for (int k 1; k n; k) { // floydfor (int i 1; i n; i) {for (int j 1; j n; j) {if (p[i][k][t - 1] true p[k][j][t - 1] true) {p[i][j][t] true;dis[i][j] 1;}}}}}// 在新图上用floyd求最短路径for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (dis[i][k] ! INF dis[k][j] ! INF dis[i][k] dis[k][j] dis[i][j]) {dis[i][j] dis[i][k] dis[k][j];}}}}cout dis[1][n] endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout fixed;cout.precision(18);solve();return 0;
}
