题解 P1476

songxiao · 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;
}