This problem was given for kanpur site.
codechef.com/problems/ACMKANPB/
please tell what is wrong with my code ??
#include <iostream>
#include <cstdio>
using namespace std;
int N,M,L;
int adj[110][110]={0};
int getbonus(int root,int* bonus,int* done,int* isvisited){
if ( isvisited[root])
return bonus[root];
isvisited[root]=1;
if ( done[root]==1)
return bonus[root];
int mx=0;
for ( int i=0;i<N;++i){
if ( adj[root][i]!=-1 && i!=root)
mx=getbonus(i,bonus,done,isvisited)+adj[root][i]>mx?getbonus(i,bonus,done,isvisited)+adj[root][i]:mx;
}
bonus[root]=mx;
done[root]=1;
isvisited[root]=0;
return mx;
}
bool flag;
void dfs(int root,int* isVisited,int *isVisited2,int count){
if(isVisited[root]){
if(count>0)
flag=true;
return;
}
if(isVisited2[root]) return;
if(flag) return;
isVisited[root]=isVisited2[root]=1;
for (int i=0;i<N;++i){
if(i==root || adj[root][i]==-1)
continue;
dfs(i,isVisited,isVisited2,count+adj[root][i]);
}
isVisited[root]=0;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
flag=false;
scanf("%d %d %d",&N,&M,&L);
for(int i=0;i<100;++i)
for(int j=0;j<100;++j)
adj[i][j]=-1;
int son[110]={0};
int bonus[110]={0};
int done[110]={0};
for( int i=0;i<M;++i){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
son[x-1]=1;
adj[x-1][y-1]=z;
}
/*for(int i=0;i<N;++i)
if(!son[i]){
bonus[i]=L;
done[i]=1;
}
*/
int isvisited[100]={0},isVisited2[100]={0};
dfs(0,isvisited,isVisited2,0);
if ( flag){
printf("Inconsistent analysis.\n");
continue;
}
for(int i=0;i<N;++i)
isvisited[i]=0;
for(int i=0;i<N;++i)
getbonus(i,bonus,done,isvisited);
int sum=0;
for(int i=0;i<N;++i)
sum+=bonus[i]+L;
printf("%d\n",sum);
for(int i=0;i<N;++i)
printf("%d ",bonus[i]+L);
printf("\n");
}
return 0;
}
i think it fails for cases like
6 1 10
1 1 2
are there any other cases for which it may fail ??
