PKU3613 Cow Relays

この手の問題は大嫌いです。
http://www.ioi-jp.org/ioi/2011/tasks/day1/garden.html
に似ています。

やることは最初と最後だけまじめに計算して間がループの繰り返しであることを利用して適当にサボるだけです。

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int p[200];
int q[200];
int cost[200];
int u[1100];
int con[1100];
int dp[300][200];
int val[300][200];
int d1[300][300];
int d2[300][300];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);c--;d--;
	for(int i=0;i<b;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		y--;z--;
		p[i]=y;q[i]=z;cost[i]=x;
		u[y]=u[z]=1;
	}
	int ind=0;
	for(int i=0;i<1100;i++){
		if(u[i])con[i]=ind++;
	}
	c=con[c];d=con[d];
	for(int i=0;i<b;i++){
		p[i]=con[p[i]];
		q[i]=con[q[i]];
	}
	for(int i=0;i<ind;i++){
		for(int j=0;j<=ind;j++){
			for(int k=0;k<ind;k++)dp[j][k]=999999999;
		}
		dp[0][i]=0;
		for(int j=0;j<ind;j++){
			for(int k=0;k<b;k++){
				dp[j+1][q[k]]=min(dp[j+1][q[k]],dp[j][p[k]]+cost[k]);
				dp[j+1][p[k]]=min(dp[j+1][p[k]],dp[j][q[k]]+cost[k]);
			}
		}
		for(int j=1;j<=ind;j++){
			val[i][j]=dp[j][i];
		}
	}
	for(int i=0;i<=ind;i++)
		for(int j=0;j<ind;j++)
			d1[i][j]=999999999;
	d1[0][c]=0;
	for(int i=0;i<=ind;i++)
		for(int j=0;j<ind;j++)
			d2[i][j]=999999999;
	d2[0][d]=0;
	for(int i=0;i<ind;i++){
		for(int j=0;j<b;j++){
			d1[i+1][q[j]]=min(d1[i+1][q[j]],d1[i][p[j]]+cost[j]);
			d2[i+1][q[j]]=min(d2[i+1][q[j]],d2[i][p[j]]+cost[j]);
			d1[i+1][p[j]]=min(d1[i+1][p[j]],d1[i][q[j]]+cost[j]);
			d2[i+1][p[j]]=min(d2[i+1][p[j]],d2[i][q[j]]+cost[j]);
		}
	}
	int ret=1999999999;
	if(ind>=a){
		printf("%d\n",d1[a][d]);
		return 0;
	}
	for(int i=0;i<ind;i++){
		for(int j=0;j<=ind;j++){
			if(d1[j][i]==999999999)continue;
			for(int k=0;k<=ind;k++){
				if(d2[k][i]==999999999)continue;
				int V=(a-k)-j;
				for(int l=2;l<=ind;l++){
					if(V%l==0&&val[i][l]<999999999)ret=min(ret,d1[j][i]+d2[k][i]+val[i][l]*(V/l));
				}
			}
		}
	}
	printf("%d\n",ret);
}

これでUSACO unsolvedは8問。