qq怎么做自己的网站,设计师培训基地,微商推广,做淘客网站企业备案题目描述 小A的工作不仅繁琐#xff0c;更有苛刻的规定#xff0c;要求小A每天早上在6#xff1a;00之前到达公司#xff0c;否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资#xff0c;小A买了一个十分牛B的空间跑路器#xff0c;每秒钟可以跑… 题目描述 小A的工作不仅繁琐更有苛刻的规定要求小A每天早上在600之前到达公司否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资小A买了一个十分牛B的空间跑路器每秒钟可以跑2^k千米k是任意自然数。当然这个机器是用longint存的所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图小A家为点1公司为点n每条边长度均为一千米。小A想每天能醒地尽量晚所以让你帮他算算他最少需要几秒才能到公司。数据保证1到n至少有一条路径。 输入输出格式 输入格式 第一行两个整数nm表示点的个数和边的个数。 接下来m行每行两个数字uv表示一条u到v的边。 输出格式 一行一个数字表示到公司的最少秒数。 思路 如果 $ f_{i,j,t} 1 $ 表示从i到j有一条长度为 $2^{t}$ 的路径 那么如果$ f_{i,k,t-1} 1$ 且$ f_{k,j,t-1} 1$ 从i到j就存在一 条长度为 $2^{t}$ 的路径让$dis_{i,j}0$即可 #include bits/stdc.h
using namespace std;
const int maxn 60 10;
int n,m,dist[maxn][maxn];
bool f[maxn][maxn][maxn];
int main() {memset(dist,10,sizeof(dist));scanf(%d%d,n,m);for (int i 1,x,y;i m;i) {scanf(%d%d,x,y);dist[x][y] 1;f[x][y][0] 1;}for (int d 1;d 64;d)for (int i 1;i n;i)for (int k 1;k n;k)for (int j 1;j n;j)if (f[i][k][d-1] f[k][j][d-1]) {f[i][j][d] true;dist[i][j] 1;}for (int k 1;k n;k)for (int i 1;i n;i)for (int j 1;j n;j) dist[i][j] min(dist[i][j],dist[i][k]dist[k][j]);printf(%d,dist[1][n]);return 0;
} 转载于:https://www.cnblogs.com/lrj124/p/8971640.html
