代码
#include <stdio.h>
#include <stdlib.h>
#define N 100
int g[N][N];
int time[N];
int maxtime[N];
int indegree[N];
typedef struct node {
int val;
node* next;
}*grapgnode;
typedef struct graph {
int size;
grapgnode* list;
}*G;
int max(int a, int b) {
if (a > b) {
return a;
}
else {
return b;
}
}
int main()
{
/********** Begin **********/
int n;
printf("请输入课程的个数：");
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
printf("请输入第%d门课程的课程时间：",i);
scanf("%d", &time[i]);
}
//构建邻接表
G g = (G)malloc(sizeof(graph));
g->size = n;
g->list = (grapgnode*)malloc(n * sizeof(node) + 1);
for (int i = 1; i <= n; i++) {
g->list[i] = (grapgnode)malloc(sizeof(node));
g->list[i]->next = NULL;
}
//初始化入度数组 并赋值
printf("请输入A门课程要在B门之前开课,输入-1 -1结束\n");
int u, v;
while (1) {
printf("A B:");
scanf("%d%d", &u, &v);
if (u == -1 && v == -1) {
break;
}
indegree[v]++;
grapgnode node = (grapgnode)malloc(sizeof(node));
node->val = v;
node->next = g->list[u]->next;
g->list[u]->next = node;
}
int target;
printf("查询编号为几的课程的最小开启时间：");
scanf("%d", &target);
//用队列保存入度为0的点
int que[1000];
int head = 0, tail = 0;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
que[tail++] = i;
if (i == target) {
goto found;
}
}
}
while (head < tail) {
int cur = que[head];
grapgnode curnode = g->list[cur]->next;
while (curnode) {
indegree[curnode->val]--;
maxtime[curnode->val] = max(maxtime[cur] + time[cur],maxtime[curnode->val]);
if (indegree[curnode->val] == 0) {
que[tail++] = curnode->val;
}
curnode = curnode->next;
}
head++;
}
goto found;
//
/********** End **********/
return 0;
found:
printf("最小时间为：%d", maxtime[target]);
return 0;
}