数据库在网站建设中的作用,wordpress建站百科,阿里巴巴与慧聪网网站建设对比,个性flash网站原题链接#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;
}
