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; }