#include<stdio.h>
#include<stdlib.h>
typedef struct _arcNode
{
    int adjvex;
    int weight;
    struct _arcNode *nextarc;
}arcNode;//定义有向弧，包含弧头标号，弧的权重（活动持续时间）
typedef struct  _vNode
{
    char data;
    arcNode *firstarc;
}vNode;//定义顶点，包含顶点信息，指向以该顶点为弧尾的第一条弧
#define  MaxVertexNum 100//最大顶点数
typedef vNode adjList[MaxVertexNum];
typedef struct _adjGraph
{
    adjList ver;
    int e, n;
}adjGraph;//定义邻接表
void createAdjGraph(adjGraph *G)
{
    scanf("%d,%d", &G->n, &G->e);
    getchar();
    for (int i = 0; i < G->n; i++)
    {
        scanf("%c ", &G->ver[i].data);
        G->ver[i].firstarc = NULL;
    }
    int a, b, w;
    for (int i = 0; i < G->e; i++)
    {
        scanf("%d,%d,%d", &a, &b, &w);
        arcNode *tmp = (arcNode*)malloc(sizeof(arcNode));
        tmp->weight = w;
        if (G->ver[a].firstarc == NULL)
        {
            tmp->adjvex = b;
            tmp->nextarc = NULL;
            G->ver[a].firstarc = tmp;
        }
        else
        {
            tmp->adjvex = b;
            tmp->nextarc = G->ver[a].firstarc;
            G->ver[a].firstarc = tmp;
        }
    }
}//创建邻接表
typedef struct  _topoSequenceS
{
    int verNum[MaxVertexNum];
    int top;
}topoSequenceS;//定义拓扑排序的存储结构，拓扑排序时，先输出的顶点标号入栈；你拓扑排序倒过来就可以
topoSequenceS *topoS = (topoSequenceS*)malloc(sizeof(topoSequenceS));
void findInDegree(adjGraph *G, int *indegree)
{
    for (int i = 0; i < G->n; i++)
    {
        arcNode *arcPos = G->ver[i].firstarc;
        while (arcPos != NULL)
        {
            indegree[arcPos->adjvex] += 1;
            arcPos = arcPos->nextarc;
        }
    }

}//查询每个顶点的入度，indegree的下标对应顶点标号；搜索时每遇到以某个顶点为弧头的弧对应弧头的入度就加一
bool  topologicalSort(adjGraph *G,int *ve)
{
    int *indegree = (int*)malloc(sizeof(int)*G->n);
    for (int i = 0; i < G->n; i++)
        indegree[i] = 0;//初始化每个顶点的入度
    findInDegree(G, indegree);
    int *tmpS = (int*)malloc(sizeof(int)*G->n);//临时存储入度为零且未输出的顶点
    int top = -1;
    for (int i = 0; i < G->n; i++)
    {
        if (!indegree[i])tmpS[++top] = i;
    }
    for (int i = 0; i < G->n; i++)
        ve[i] = 0;//初始化每个顶点的最早开始时间
    topoS->top = -1;//初始化存储拓扑序列的栈
    int i = 0;
    while (top != -1)//拓扑排序
    {
        i = topoS->verNum[++topoS->top] = tmpS[top--];//入度为零，弹出，也就是输出对应顶点
        arcNode *arcPos = G->ver[i].firstarc;
        while (arcPos != NULL)//遍历所有以顶点i为弧尾的弧
        {
            if (!(--indegree[arcPos->adjvex]))tmpS[++top] = arcPos->adjvex;//所有以顶点i为直接前驱的顶点的入度减一
            if (ve[i] + arcPos->weight > ve[arcPos->adjvex])ve[arcPos->adjvex] = ve[i] + arcPos->weight;//求所有以顶点i为直接前驱的顶点的最早开始时间
            /*
            貌似与前面求事件最早发生时间ve(j)和最迟发生时间vl(j)不同，实则一样，
            因为在拓扑排序过程，会遍历到所有的弧，每次记录某个顶点（arcPos->adjvex）最早开始时间的，结束时存储的就是最大的，
            
            */
            arcPos = arcPos->nextarc;
        }
    }
    if (topoS->top < G->n - 1)return false;//有回路
    else
        return true;
}
bool criticalPath(adjGraph *G)
{
    int *ve = (int*)malloc(sizeof(int)*G->n);//定义存储顶点最早开始时间数组
    int *vl = (int*)malloc(sizeof(int)*G->n);//定义存储顶点最迟开始时间数组
    if (!topologicalSort(G, ve))return false;//拓扑排序，并求出ve
    for (int i = 0; i < G->n; i++)
    {
        vl[i] = ve[G->n - 1];
    }//初始化所有顶点的最迟开始时间，设为最长路径长度
    int j = 0;
    while (topoS->top != -1)
    {
        j = topoS->verNum[topoS->top--];//你拓扑排序输出
        printf("\n%c\n", G->ver[j].data);
        arcNode *arcPos = G->ver[j].firstarc;
        while (arcPos != NULL)//遍历所有以j为弧尾的弧
        {
            if (vl[arcPos->adjvex] - arcPos->weight < vl[j])
                vl[j] = vl[arcPos->adjvex] - arcPos->weight;//记录j的最迟开始时间
                                                            /*
                                                            貌似与前面求事件最早发生时间ve(j)和最迟发生时间vl(j)不同，实则一样，
                                                            因为在拓扑排序过程，会遍历到所有的弧，每次记录某个顶点（j）最迟开始时间的，结束时存储的就是最小的，

                                                            */
            arcPos = arcPos->nextarc;
        }
    }
    int ee = 0; int el = 0;
    for (int i = 0; i < G->n; i++)
    {
        arcNode *arcPos = G->ver[i].firstarc;
        while (arcPos != NULL)
        {
            ee = ve[i];//活动<i,arcPos->adjvex>的最早开始时间
            el = vl[arcPos->adjvex] - arcPos->weight;//活动<i,arcPos->adjvex>的最迟开始时间
            if (ee == el)printf("%c--%c:%d\n", G->ver[i].data, G->ver[arcPos->adjvex].data, arcPos->weight);
            arcPos = arcPos->nextarc;
        }
    }
}
#include<conio.h>
int main(void)
{
    freopen(".\\in.txt", "r", stdin);
    adjGraph *G = (adjGraph*)malloc(sizeof(adjGraph));

    createAdjGraph(G);
    fclose(stdin);
    for (int i = 0; i < G->n; i++)
    {
        printf("%c->", G->ver[i].data);
        arcNode *pos = G->ver[i].firstarc;
        while (pos != NULL)
        {
            printf("%c->", G->ver[pos->adjvex].data);
            pos = pos->nextarc;
        }
        printf("\n");
    }//输出文本中存储的图邻接表
    
    if (!criticalPath(G))
        printf("Error!There is a circuit!\n");
    
    getch();
    return 0;
}