某公司需要在项目中引入某开源工程,需要评估该开源工程中某模块的编译时间,
当前已知该项目中每个模块的编译时间以及依赖模块列表,在拥有无限数量的并行
任务情况下,求某个指定模块的最短编译时间。
若模块间存在循环依赖或依赖模块不存在,则无法完成编译,返回-1;
输入描述:
第一行输入为目标模块名;
以后每一行输入定义一个模块,包含模块的名字,编译时间,依赖模块列表,用逗号隔开,若依赖模块列表不存在,则表示可以独立编译,例如:
module2,10,module1
module1,10
模块名只包含字母和数字且至少包含一个字符,模块数量不超过50000个。
输出描述:
输出最短编译时间,若无法完成编译则输出-1;
例如:输入
module3
module1,10
module2,5
module3,10,module1,module2
输出:
20
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct module_t
{
char name[255];
int time;
int isCompiled;
struct module_t *next;
struct module_t *depends;
}module_t;
int parseInput( module_t **mds, char * buf , char* modName )
{
int state = 0;
module_t * md = (module_t*)malloc(sizeof(module_t));
md->next = md->depends = NULL;
md->isCompiled = 0;
char *p = strtok(buf,",");
while( p )
{
switch( state )
{
case 0 :
//此处应该校验模块名是否合法
strcpy(md->name , p );
state++;
break;
case 1:
md->time = atoi(p);
state++;
break;
default:
{
//此处应该校验模块名是否合法
module_t* dp = (module_t*)malloc( sizeof(module_t));
dp->next = dp->depends = NULL;
strcpy(dp->name,p);
module_t **pp = &md;
for( module_t *prev = *pp ; prev!=NULL;prev = *pp )
{
pp=&prev->depends;
}
dp->depends = *pp;
*pp = dp;
}
break;
}
p=strtok(NULL,",");
}
if (*mds==NULL)
*mds = md;
else {
md->next = *mds;
*mds = md;
}
if (strcmp(md->name,modName) == 0 )
return 2;
return 1;
}
int calculateCompileTime( module_t *mds , module_t *md ,char *lastModName,int *nextTime)
{
int time = 0;
int found = 0;
module_t *depends = md->depends;
time=md->time;
while (depends !=NULL) {
//循环依赖
if ( strcmp(lastModName,depends->name) == 0 )
{
printf("-1\n");
exit(-1);
}
module_t *next = mds;
while( next != NULL )
{
if ( strcmp(next->name , depends->name ) == 0 )
{
//?并行任务中只计算未编译过的模块和编译时间长的模块
if ( next->time >= *nextTime && next->isCompiled == 0 )
{
time+=calculateCompileTime(mds,next,md->name,nextTime);
*nextTime = next->time;
next->isCompiled = 1;
}
found = 1;
}
next = next->next;
}
if ( found == 0 )
{
printf("-1\n");
exit(-1);
}
depends = depends->depends;
}
return time;
}
int main()
{
char modName[255];
char inbuf[1024];
module_t *modList = NULL;;
int state = 0;
do
{
scanf("%s",inbuf);
if ( state == 0 )
{
strcpy(modName,inbuf);
state++;
}
else if ( parseInput(&modList,inbuf,modName)==2 )
{
int nextTime = modList->time;
printf("%d\n",calculateCompileTime(modList,modList,modList->name,&nextTime));
break;
}else if ( state > 50000 )
{
printf("You're fucking typing too much!!!\n");
break;
}
}while(1);
while (modList!=NULL )
{
module_t *next = modList->next;
while(modList->depends!=NULL)
{
module_t *pp = modList->depends->depends;
free(modList->depends);
modList->depends = pp;
}
free(modList);
modList = next;
}
return 0;
}