AOE网上的关键路径 Time Limit: 1000MS Memory Limit: 65536KB Problem Description
一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。 AOE(Activity On Edge)网：顾名思义，用边表示活动的网，当然它也是DAG。与AOV不同，活动都表示在了边上，如下图所示：
如上所示，共有11项活动（11条边），9个事件（9个顶点）。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点（源点）和只有一个出度为零的点（汇点）。 关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示，1 到2 到 5到7到9是关键路径（关键路径不止一条，请输出字典序最小的），权值的和为18。
Input
这里有多组数据，保证不超过10组，保证只有一个源点和汇点。输入一个顶点数n(2<=n<=10000),边数m(1<=m <=50000),接下来m行，输入起点sv，终点ev,权值w（1<=sv,ev<=n,sv != ev,1<=w <=20)。数据保证图连通。
Output
关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，请输出字典序最小的）。
Example Input
9 11 1 2 6 1 3 4 1 4 5 2 5 1 3 5 1 4 6 2 5 7 9 5 8 7 6 8 4 8 9 4 7 9 2
Example Output
18 1 2 2 5 5 7 7 9
代码：
#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct node { int to, w, next;//下一个城市，权值，下一个城市对应的map下标 }ST; ST map[50055]; int head[10055];//用来标记起始点对应的map下标 int a[10055];//数组模拟队列 int l, r; int nex[10055];//下一个城市 int dist[10055];//最长路径 int vis[10055];//用来标记存储了的城市 int main() { int n, m, cnt, u, v, wi, i; while(~scanf("%d %d", &n, &m)) { memset(head, -1, sizeof(head)); memset(dist, 0, sizeof(dist)); memset(vis, 0, sizeof(vis)); memset(nex, 0, sizeof(nex)); cnt = 0; while(m--) { scanf("%d %d %d", &u, &v, &wi);//前向星储存图，逆着存储，原因是为了求最小的字典序 map[cnt].to = u;//目的城市 map[cnt].w = wi;//权值 map[cnt].next = head[v];//指向目的城市的下标 head[v] = cnt++;//当前起始点城市的下标存起来 } l = r = 0;//初始化头和尾 a[r++ % 10055] = n;//入队列 vis[n] = 1;//标记一下 while(l < r) { u = a[l++ % 10055];//出队列 vis[u] = 0;//让标记撤销 for(i = head[u]; i != -1; i = map[i].next) { if(dist[map[i].to] < dist[u] + map[i].w || (dist[map[i].to] == dist[u] + map[i].w && nex[map[i].to] > u))//更新最长距离，如果最长距离一样，判断目的城市，和起始城市谁的编码小 { dist[map[i].to] = dist[u] + map[i].w;//更新dist的值 nex[map[i].to] = u;//谁的编号小，目的城市就指向谁，因为是逆着的，nex[]里边的城市，相当于起始城市，u相等于目的城市 所以逆着建图的原因在这里,这样求出来的字典序最小 if(!vis[map[i].to])//如果没有入队列，就入队列，顺便标记一下 { a[r++ % 10055] = map[i].to; vis[map[i].to] = 1; } } } } printf("%d\n", dist[1]);//输出最大路径长度 for(i = 1; nex[i]; i = nex[i]) { printf("%d %d\n", i, nex[i]);//输出路径编号 } } return 0; }