読者です 読者をやめる 読者になる 読者になる

Sports Days 2.0 (AOJ2432)

典型良問.
累乗系の本質は結合法則.ただの乗算だけでなく,a->bへi回移動での(max,min)長さ とかは典型.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef vector<int> vi;
typedef vector<vi> mat;
mat op(mat a,mat b){
	int N=a.size();
	mat c=a;
	rep(i,N) rep(j,N) rep(k,N) if(a[i][j]>=0&&b[j][k]>=0) chmax(c[i][k],a[i][j]+b[j][k]);
	return c;
}
int getmx(mat a){
	int N=a.size();
	int mx=-1;
	rep(i,N) rep(j,N) chmax(mx,a[i][j]);
	return mx;
}
int main(){
	int N,M,K;
	int dp[151][150]={};
	int from[151][150]={};
	cin>>N>>M>>K;
	mat m(N,vi(N,0));
	rep(i,N) rep(j,N) m[i][j]=-1;
	rep(i,M){
		int a,b,c;
		cin>>a>>b>>c;
		chmax(m[a][b],c);
	}
	rep1(i,150) rep(j,N) dp[i][j]=-1;
	rep(i,150){
		rep(v,N) rep(u,N){
			if(m[v][u]<0||dp[i][v]<0) continue;
			if(dp[i+1][u]<dp[i][v]+m[v][u]){
				dp[i+1][u]=dp[i][v]+m[v][u];
				from[i+1][u]=v;
			}
		}
		int mx=-1;
		rep(v,N) chmax(mx,dp[i+1][v]);
		if(mx>=K){
			if(i>100){
				cout<<i<<endl;
				return 0;
			}else{
				int x=-1;
				rep(v,N) if(mx==dp[i+1][v]) x=v;
				vector<int> ans;
				ans.pb(x);
				for(int j=i+1;j>0;j--) ans.pb(from[j][x]),x=from[j][x];
				reverse(all(ans));
				cout<<i+1<<endl;
				rep(i,ans.size()) cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
				return 0;
			}
		}
		if(i==149&&mx==-1){
			puts("-1");
			return 0;
		}
	}
	mat ms[20];
	ms[0]=m;
	rep(i,19) ms[i+1]=op(ms[i],ms[i]);
	mat x(N,vi(N,-1));
	rep(i,N) x[i][i]=0;
	int ans=0;
	for(int i=19;i>=0;i--){
		mat nx=op(x,ms[i]);
		if(getmx(nx)<K){
			x=nx;
			ans+=(1<<i);
		}
	}
	cout<<ans+1<<endl;
}