I have been trying this problem http://www.spoj.pl/problems/FPOLICE/. My idea is to modify the single source shortest path problem to 2-D.So instead of using an array to denote the shortest distance I am using a 2-D matrix where state[i][j] indicates the shortest path from the source to the ith node with still having j time left.(The upper limit on left time is denoted by t) Finally I check the last row (state[n-1][j] for all j=t to j=0 ) the minimum cost.If the minimum cost comes out to be INFINITY then there is no way to reach the destination with atleast 0 time remaining.If minimum costs occur for several values of j i pick up the j which is larger.That is the case which yields more remaining time ( i.e. minimum time).For the single source shortest path I started with dijikistra but then switched to bellman-ford for simplicity.(Doesn't looks like o(n^2*t) will be problem)

UPD: Code modified to fix some bugs

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>


#define PR(x) printf(#x"=%d\n",x)
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(int i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(int i=0;i<n;i++)printf(#x"[%d]=\t%d\n",i,x[i])
const int INF=2<<29;

int costMatr[101][101];
int timeMatr[101][101];
using namespace std;

int main()
	{
	int n;
	int t;
	/*Input section */
	int tstcase;
	scanf("%d",&tstcase);
	while(tstcase--){
	scanf("%d %d",&n,&t);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			{
			scanf("%d",&timeMatr[i][j]);
			}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			{
			scanf("%d",&costMatr[i][j]);
			}
	
	
	/*End input */	
	
	int state[101][251]; //state[i][j] represents cost from source node to ith node with j time remaining
	for(int i=1;i<n;i++) 
		for(int j=0;j<=t;j++)
		{
		
		 state[i][j]=INF; //initialize all states to infinity
		
		 }
		 
	for(int i=0;i<=t;i++) state[0][i]=0; //cost to reach 0th node will be 0 regardless of time left
	for(int i=1;i<n;i++)
	if(t-timeMatr[0][i]>=0) state[i][t-timeMatr[0][i]]=costMatr[0][i]; //initialize state matrix for neighbours of source nodeh

	/*DP begin */
	for(int k=t;k>=0;k--)
	
		{
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
		if(i==j) continue;
		 
			if(costMatr[i][j]+state[i][k]<=state[j][k])
				{
				
				if(k-timeMatr[i][j]>=0) {
				#ifndef ONLINE_JUDGE
				printf("Distance to %dth node updated for time %d. previous value at this state=%d",j,k,state[j][k]);
				#endif
				state[j][k-timeMatr[i][j]]=costMatr[i][j]+state[i][k];
				#ifndef ONLINE_JUDGE
				printf("New value for this time %d =%d\n",k-timeMatr[i][j],state[j][k]);
				#endif
				}
				}
		
			
		}
	}
	
	/*DP END*/
	/*possible answer in state[n-1][t] where t is all possible values of remaining time */
	
	int minCost=INF;
	int minTime=t;	
	for(int k=t;k>=0;k--)
	{
	if(state[n-1][k]<minCost)
	{
	minCost=state[n-1][k];
	minTime=k;
	}
	}
	if(minCost==INF)
	puts("-1");
	else
	printf("%d %d\n",minCost,t-minTime);
	}
	}

Kindly suggest some test cases where my algorithm might be failing.I am almost sure my idea of 2-D Dp is correct,just that I am not able to implement it properly.

UPD: Got the bug.TYpo in if(costMatr[i][j]+state[i][k]<=state[j][k]) should have been if(costMatr[i][j]+state[i][k]<=state[j][k-timeMatr[i][j]])

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>


#define PR(x) printf("")
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(int i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(int i=0;i<n;i++)printf("")
using namespace std;
typedef long long ll;
int main() { 
string s1,s2;
cin>>s1;cin>>s2;
int idx=1;
string subst;
char ch=s1[0];
int len1=s1.length();
int len2=s2.length();
int lenC=1;
while(idx<len1&&ch!=s1[idx++]) lenC++;
PR(lenC);
if(lenC!=len1) {

for(int j=1;j<lenC&&j<len1;j++){
while(len1%lenC!=0) lenC++;
for(int k=j+lenC;k<len1;k+=lenC){
if(s1[j]!=s1[k]) {
//printf("VIolation at %d %d char values %c %c\n",j,k,s1[j],s1[k]);
k-=lenC;
lenC+=1;

}

}
}

}
lenC=min(len1,lenC);
int count1=0;
for(int i=1;i*lenC<=len1;i++) count1++;
PR(lenC);
PR(count1);
subst=s1.substr(0,lenC);
if(len2%lenC!=0||len2<lenC) {
			puts("0");
			return 0;
		}
bool flg=false;
for(int i=0;i<lenC;i++){
for(int j=i;j<len2;j+=lenC)
if(s2[j]!=subst[i]){
//printf("VIolation at %d %d char values %c %c\n",i,j,s2[j],subst[i]);
flg=true;
break;
}
if(flg) break;
}
if(flg) {
		puts("0");
		return 0;
	}
int num2=0;
for(int i=1;i*lenC<=len2||i*lenC<=len1;i++) if(len2%(i*lenC)==0&&len1%(i*lenC)==0)num2++;
int ans=num2;
printf("%d\n",ans);
}

I am getting wrong answer on pretest 9.The pretest is very long so can't see the complete test case. My solution is based on the following approach 1.if a substring x is a divisor of a string S then it will be either a.Shortest divisor of S(in terms of length) b.It can be broken down into smaller divisors based on the constraint for all divisor length l S.length()%l==0

I find out the smallest divisor in either string,then check if it is a divisor in the other string,if it is not then the strings dont have any common divisor.In case it is a divisor then i combine the smaller divisor to get bigger divisors such that the length of bigger divisors divide both S1.length() and S2.length() where S1 and S2 are the input strings.