#include<iostream>
#include<cstring>
#include<cstdio>
#include "stack.h"
using namespace std;
#define maxN 100001
struct ArcNode//表结点
{
int citynumber;//城市编号
int price;//边上的权值
ArcNode *nextArc;//指向下一个邻接顶点
};
struct VNode//头结点
{
int citynumber;//城市编号
int weight;//该点的权值
int inDegree;//该点的入度
int nextcity;//该城市的下一个城市
ArcNode *firstArc;//指向第一个邻接顶点
};
struct AdjList//邻接表
{
VNode city[maxN];//头结点数组
int n, e;//顶点数, 边数
};
int creat(AdjList *adjlist)//创建邻接表
{
int n, m;
int a, b, price;
std::cin >> n >> m;//输入顶点数和边数
adjlist->n = n;
adjlist->e = m;
for (int i = 1; i <= n; i++)//初始化头结点(使用第1至n个)
{
adjlist->city[i].citynumber = i;//将n个城市编号赋值为1~n
adjlist->city[i].firstArc = NULL;
adjlist->city[i].weight = 0;
adjlist->city[i].nextcity = maxN;//将下一个节点设成最大,方便之后的赋值
adjlist->city[i].inDegree = 0;
}
for (int i = 0; i < m; i++)//初始化表结点(注意:表结点是无序的!)
{
std::cin >> a >> b >> price;//边的起始、终止、权值
ArcNode *arcnode = new ArcNode;
arcnode->citynumber = b;
arcnode->price = price;
arcnode->nextArc = adjlist->city[a].firstArc;
adjlist->city[a].firstArc = arcnode;
adjlist->city[b].inDegree++;
}
return n;
}
int quanzhi(AdjList *adjlist, int head)//递归求解某一点的权值
{
ArcNode *p = adjlist->city[head].firstArc;
if (p == NULL) return 0;//出度为0的点权值为0
while (p != NULL)
{
if (adjlist->city[p->citynumber].weight == 0) adjlist->city[p->citynumber].weight = quanzhi(adjlist, p->citynumber);//已计算出权值的点无需再计算
if (p->price + adjlist->city[p->citynumber].weight > adjlist->city[head].weight )
{
adjlist->city[head].weight = p->price + adjlist->city[p->citynumber].weight;
adjlist->city[head].nextcity = p->citynumber;
}
else if (p->price + adjlist->city[p->citynumber].weight == adjlist->city[head].weight && adjlist->city[head].nextcity > p->citynumber)//相等时按字典序
{
adjlist->city[head].weight = p->price + adjlist->city[p->citynumber].weight;
adjlist->city[head].nextcity = p->citynumber;
}
p = p->nextArc;
}
return adjlist->city[head].weight;
}
int main()
{
std::ios::sync_with_stdio(false);
int n;//n为总结点数
int max = 0, maxnow;
int way[maxN];//记录最终路径的数组
int waynow[maxN];//记录暂时路径的数组
int k;
memset(way, 0, maxN * sizeof(int));
AdjList *adjlist = new AdjList;
n = creat(adjlist);
Stack stack;//此栈用来存放入度为0的顶点
for (int i = n; i > 0; i--)//从后往前存,栈中元素会从前往后弹出,所以当后面的路径长度与前面相同时,一定是选用前面的
{
if (adjlist->city[i].inDegree == 0)
stack.push(adjlist->city[i].citynumber);
}
while (!stack.empty())
{
memset(waynow, 0, maxN * sizeof(int));//将waynow全部置零
k = stack.pop();
maxnow = quanzhi(adjlist, k);
if (maxnow > max)
{
max = maxnow;
VNode q = adjlist->city[k];
int j = 1;
while (q.firstArc != NULL)
{
waynow[j++] = q.citynumber;
q = adjlist->city[q.nextcity];
}
waynow[j++] = q.citynumber;//储存最后一个节点
memset(way, 0, maxN * sizeof(int));//此处应该重新置零!!!!!否则当maxway长度小于max时一部分值无法被覆盖
for (int i = 1; waynow[i] != 0; i++)
{
way[i] = waynow[i];
}
}
}
for (int i = 1; way[i] != 0; i++)
{
printf("%d\t",way[i]);
}
return 0;
}