自动搬运

查看原文

来自洛谷，原作者为

	songxiao 我不生产主页，我只是内容的搬运工

搬运于2025-08-24 21:25:31，当前版本为作者最后更新于2022-02-11 22:40:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很多的题解都说“剧情结束点不是所有节点，节点数还要多一个”但是并没有解释。我来说一下，其实剧情结束点确实是从 $1$ 到 $n$，但是还有一个总的剧情开始的节点，所以实际是 $0$ 到 $n$。如果下标从 $1$ 开始，就可以理解为 $1$ 到 $n+1$。

然后就是最长路板子，可以参考 P1807 最长路。

AC code:

#include<bits/stdc++.h>
using namespace std;
int n,m,dis[1005][1005];
int main()
{
	cin>>n>>m;
    for(int i=1;i<=n+1;i++)//初始化
        for(int j=1;j<=n+1;j++)
        {
            if(i==j)
                dis[i][j]=0;
            else
                dis[i][j]=1e9;
        }
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		dis[u][v]=min(dis[u][v],-w);//谨防重边（不一定有）
	}
	for(int k=1;k<=n+1;k++)
	{
		for(int i=1;i<=n+1;i++)
		{
			for(int j=1;j<=n+1;j++)
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
    cout<<-dis[1][n+1]<<' '<<endl;
    for(int i=1;i<=n+1;i++)
    	if(dis[1][i]+dis[i][n+1]==dis[1][n+1])
    		cout<<i<<' '; 
	return 0;
}