本文共 818 字，大约阅读时间需要 2 分钟。

题目链接：

题目大意：略。

解题思路：关键路径（最长路径 + 逆向（字典序））。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxm=50009, maxn=1e4+10;struct node{    int u,v,w;}es[maxm];int n,m,d;int in[maxn], out[maxn], dis[maxn], pre[maxn];void init(){    mem(pre,-1), mem(dis,0), mem(in,0), mem(out,0);}int rdijkstra(){    int f;    for(int i=1;i<=n;i++) // n-1条边；最多需要(n-1)条边更新,所以i不能从2开始,要从1开始,多检测一次才知道是否有环    {        f=0;        for(int j=0;j
     
      dis[es[j].v])            {                f=1;                dis[es[j].v]=dis[es[j].u]+es[j].w;                pre[es[j].v]=es[j].u; // 类似 pre[i]=s; 记录前驱            }            else if(dis[es[j].u]+es[j].w==dis[es[j].v] && es[j].u
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/82470296 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！