#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N=75;const int inf=0x3f3f3f3f;//为了方便memset的使用，inf不可以开成1e9int n,m,u,v,t;int x,q,c,d;int init[N][N];int ans[N][N];int minn(int x,int y){ return x<y?x:y;}void mul(int a[N][N],int b[N][N])//矩阵乘法，仔细观察会发现转移方程像极了floyd{ int c[N][N]; memset(c,inf,sizeof(c)); for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c[i][j]=minn(c[i][j],a[i][k]+b[k][j]); memcpy(a,c,sizeof(c));}int main(){ scanf("%d%d",&n,&m); memset(init,inf,sizeof(init)); for(int i=1;i<=n;i++) init[i][i]=0; for(int i=1;i<=m;i++) {scanf("%d%d%d",&u,&v,&t);init[u][v]=minn(init[u][v],t); } scanf("%d%d",&x,&q); x=minn(x,n); memset(ans,inf,sizeof(ans)); for(int i=1;i<=n;i++) ans[i][i]=0; while(x)//矩阵快速幂 {if(x&1) mul(ans,init);mul(init,init);x>>=1; } for(int i=1;i<=q;i++) {scanf("%d%d",&c,&d);if(ans[c][d]==inf) puts("-1");else printf("%d\n",ans[c][d]); } return 0;}【Autobus 方法记录】
推荐阅读
- 元气骑士战利品箱子获取方法
- 三星手机截屏怎么操作方法（三星敲击截图)
- 2022年实时最新省市区县乡镇街道geojson行政边界数据获取方法
- 含开启测试模式失败的解决办法 Windows开启关闭测试模式的方法
- 学生怎样赚钱（13岁赚500元的方法)
- 扣扣群红包提醒怎么设置方法（微信红包怎么提醒红包来了)
- 学生党在家赚钱的方法（动动手指在家就能赚钱)
- 学生有什么赚钱的方法（大学生赚钱小项目)
- MybatisPlus生成主键策略方法
- 小米手环怎么使用（小米手环操作方法)