本文主要是介绍SDUT-2498-AOE网上的关键路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
用的SPFA ，加个判断字典的
用的是反向建图的方式，从终点访问到起点
用数组模拟邻接表
第一道实际的SPFA的题啊，加油啊
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#define Maxn 10010
#define Maxm 10010
#define Max 10100
using namespace std;
int head[Maxm],bj[Maxn],dis[Maxn];
int pos[Maxn];
int op[Maxn];
int din[Maxn], dout[Maxn];
int n,m;
struct node
{int v, w, next;
}ls[50500];int aa[Maxn];
void SPFA()
{int q, z;for(int i = 1;i <= n; i++){if(din[i] == 0)q = i;if(dout[i]==0)z = i;}queue<int>a;for(int i = 0; i <= n; i++){dis[i] = -9999999;op[i] = 9999999;}bj[q] = 1;dis[q] = 0;a.push(q);while(!a.empty()){int top = a.front();a.pop();pos[top]++;bj[top] = 0;for(int i = head[top]; i!=-1;i = ls[i].next){if(dis[ls[i].v] <= dis[top] + ls[i].w){if(dis[ls[i].v] < dis[top] + ls[i].w){dis[ls[i].v] = dis[top] + ls[i].w;op[ls[i].v] = top;if(!bj[ls[i].v]){bj[ls[i].v] = 1;a.push(ls[i].v);}}else{if(top < op[ls[i].v]){op[ls[i].v] = top;if(!bj[ls[i].v]){bj[ls[i].v] = 1;a.push(ls[i].v);}}}}}}int num = 0;int tmp = z ;while(tmp != q){aa[num++] = tmp;tmp= op[tmp] ;}aa[num] = q;printf("%d\n",dis[z]) ;for(int i = 0 ; i< num;i++){printf("%d %d\n",aa[i],aa[i + 1]) ;}}
int main()
{while(~scanf("%d%d",&n,&m)){memset(head,-1,sizeof(head));memset(pos,0,sizeof(pos));memset(din,0,sizeof(din));memset(dout,0,sizeof(dout));int k = 0;while(m--){int u, v, w;scanf("%d%d%d",&u,&v,&w);ls[k].v = u;ls[k].w = w;ls[k].next = head[v];head[v] = k++;din[u]++;dout[v]++;}SPFA();}return 0;
}
这篇关于SDUT-2498-AOE网上的关键路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
