有哪些公司的网站做的比较好,个人网站可以收费吗,一个公司网站设计需求,小程序注册完成后如何制作Description xz是一个旅游爱好者#xff0c;这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢#xff1f;据说和非负整数的个数是一样多的。xz想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有n个…Description xz是一个旅游爱好者这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢据说和非负整数的个数是一样多的。xz想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有n个房间用1到n的正整数编号。楼层之间用电梯连接电梯只能上行不能下行或者同层移动。下楼一般自行解决电梯用(u,v,w)的形式给出表示对于任意正整数i有第i层的房间u到第iw层的房间v有一部电梯。电梯只能从起点开往终点不能中途停留。 xz想要观赏城市全景至少需要登上第m层楼即最终需要到达的楼层数≥m。由于乘坐电梯要缴纳高额的费用而如果花销太大回家就没法报账了xz希望乘坐电梯的次数最少。现在xz在第0层的1号房间你需要求出这个最少的乘坐次数。 Input 第一行包含一个正整数T表示数据的组数。接下来的数据分为T个部分。每个部分第一行包含两个正整数n和m意义见题目描述。接下来n行每行包含n个非负整数。这n行中第i行第j个数为Wi,j如果wi,j非零则表示有电梯(i,j,Wi,j)。同一行各个数之间均用一个空格隔开。 Output 对于每组数据输出一行一个正整数最少的乘坐次数。 Sample Input 2 6 147 0 1 0 50 0 0 0 0 1 0 0 0 20 0 0 0 0 0 0 0 0 0 1 50 0 0 0 8 0 0 0 0 0 0 0 3 6 152 0 1 0 50 0 0 0 0 1 0 0 0 20 0 0 0 0 0 0 0 0 0 1 50 0 0 0 8 0 0 0 0 0 0 0 3 Sample Output 9 10 【样例说明】 第一组数据中使用电梯的顺序为1→2→3→1→2→3→1→4→6→6第二组数据中使用电梯的顺序为1→2→3→1→2→3→1→4→5→4→6。第二组数据最后到达了153层但是没有更短的路径使得恰好到达152层因此答案为10。 HINT 有如下几类具有特点的数据 1、有10%的数据所有的n2 2、有20%的数据m≤3000 3、有20%的数据对于满足1≤i,j≤n的整数i和j若wi,j≠0则有wi,j≥1015 4、有30%的数据所有的n40。以上各类数据均不包含其他类数据。对于所有数据T51≤n≤1001≤m≤1018对于满足1≤i,j≤n的整数i和j有0≤wi,j≤1018。数据保证能够到达m层或更高的楼层。 /*f[p][i][j]表示用了p次电梯从i房间到j房间的最高楼层。f[p][i][j]max(f[p/2][i][k],f[p/2][k][j])然后用矩阵乘法算f[2],f[4],f[8]... 直到某个f第一行出现大于m的数。然后用二进制拆分求出答案。
*/
#includecstdio
#includeiostream
#includecstring
#define N 110
#define lon long long
#define inf 1000000000000000000LL
using namespace std;
int n,cnt;
lon m;
lon read(){lon num0,flag1;char cgetchar();while(c0||c9){if(c-)flag-1;cgetchar();}while(c0c9){numnum*10c-0;cgetchar();}return num*flag;
}
struct M{lon v[N][N];M(){memset(v,0,sizeof(v));}
}f[N];
M operator*(M a,M b){M c;for(int i1;in;i)for(int j1;jn;j){c.v[i][j]-inf;for(int k1;kn;k)c.v[i][j]max(a.v[i][k]b.v[k][j],c.v[i][j]);if(c.v[i][j]m) c.v[i][j]m;}return c;
}
bool check(M x){for(int i1;in;i)if(x.v[1][i]m) return true;return false;
}
int main(){int T;scanf(%d,T);while(T--){nread();mread();for(int i1;in;i)for(int j1;jn;j){f[1].v[i][j]read();if(!f[1].v[i][j]) f[1].v[i][j]-inf;}for(cnt1;;cnt){f[cnt1]f[cnt]*f[cnt];if(check(f[cnt1])) break;}M tf[1];lon ans1;for(int icnt;i;i--){M xt*f[i];if(!check(x)){for(int j1;jn;j)for(int k1;kn;k)t.v[j][k]x.v[j][k];ans1LL(i-1);}}coutans1endl;}return 0;
} 转载于:https://www.cnblogs.com/harden/p/6643500.html
