【jzoj 5088】【GDOI 2017第4ラウンドシミュレーションday 2】【最小エッジ権和】【図論】

テーマの大意
n個の点m個の辺の有向図があり、各辺には互いに異なる辺権wがあり、q個の質問があり、点aからc個を超えない辺から点bまでを通過することを要求し、通過する辺権を増加し、できるだけ小さくすることを要求し、最小の辺権和を求め、合法的な案がなければ-1を出力する.
問題を解く構想.
f[i][j][k]表示iからjまでk歩を歩く費用を、小さい頃から大きく加えながら、影響のある状態jが必ずエッジの終点であることを発見し、暴力的に更新すればよい.
code

#include
#include
#define min(a,b) ((a
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=150+9,mm=5*1e3+9,inf=1e9;
int n,m,q,f[mn][mn][mn];
struct rec{
    int u,v,w;
};
rec a[mm];
bool cmp(rec x,rec y){
    return x.w<y.w;
}
int main(){
    //freopen("sum.in","r",stdin);
    //freopen("sum.out","w",stdout);
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    fo(i,1,m)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    sort(a+1,a+m+1,cmp);
    fo(i,1,n)fo(j,1,n)fo(k,0,n)f[i][j][k]=inf;
    fo(i,1,n)fo(k,0,n)f[i][i][k]=0;
    fo(i,1,m){
        fo(j,1,n)fo(k,1,n)f[j][a[i].v][k]=min(f[j][a[i].v][k],f[j][a[i].u][k-1]+a[i].w);
    }
    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]);
    int u,v,w;
    fo(i,1,q){
        scanf("%d%d%d",&u,&v,&w);w=min(w,n-1);
        if(f[u][v][w]==inf)printf("-1
");
        else printf("%d
",f[u][v][w]);
    }
    return 0;
}