题目描述

有一张n个点m条边的有向图，每条边有一个互不相同的边权w，有q个询问，要求你从点a经过不超过c条边到点b，要求经过的边权递增并和尽量小，求出最小的边权和，如果没有合法方案则输出-1。

水题

按边权从小到大加入做floyd即可。

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; const int maxn=150+10,maxm=5000+10,inf=100000000; struct dong{ int x,y,z; } e[maxm]; int f[maxn][maxn][maxn]; int i,j,k,l,t,n,m,q,x,y,z,ans; bool cmp(dong a,dong b){ return a.z<b.z; } int main(){ freopen("sum.in","r",stdin);freopen("sum.out","w",stdout); scanf("%d%d%d",&n,&m,&q); fo(i,1,m) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); sort(e+1,e+m+1,cmp); fo(i,1,n) fo(j,1,n) fo(k,0,n) f[i][j][k]=inf; fo(i,1,n) f[i][i][0]=0; fo(t,1,m){ x=e[t].x;y=e[t].y;z=e[t].z; fo(i,1,n) fo(k,0,n) f[i][y][k+1]=min(f[i][y][k+1],f[i][x][k]+z); } fo(i,1,n) fo(j,1,n) fo(k,1,n) f[i][j][k]=min(f[i][j][k],f[i][j][k-1]); while (q--){ scanf("%d%d%d",&x,&y,&z); z=min(z,n); ans=f[x][y][z]; if (ans==inf) printf("-1\n");else printf("%d\n",ans); } }