题解：P1807 最长路

kingho11 · 2024-07-20 11:22:46 · 题解

前置知识：dijkstra。

没有做过这道题目的人可以先做做【模板】单源最短路径（弱化版）这道题。

接下来，进入正题，因为这道题目的图是 DAG（有向无环图），所以这道题目是一道 dijkstra 模板题，只需要对 dijkstra 的部分条件进行更改即可，要注意，重载运算符的符号到底是什么。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long n,m,s,dis[N];
struct uuu{
    long long u,w;
    bool operator < (const uuu &a) const//要以长度为排序的值
    {
        return a.w>w;
    }
};
struct uu{
    long long v,w;
};
priority_queue <uuu,vector <uuu>,less<uuu> > pq; 
vector <uu> v[N];
void dijkstra()//dijkstra 模板
{
    pq.push((uuu){1,0});
    dis[1]=0;
    while(!pq.empty())
    {
        uuu o=pq.top();
        pq.pop();
        long long u=o.u;
        for(long long i=0;i<v[u].size();i++)
        {
            long long v2=v[u][i].v,dis2=v[u][i].w;
            if(dis[v2]<dis[u]+dis2)
            {
                dis[v2]=dis[u]+dis2;
                pq.push((uuu){v2,dis[v2]});
            }
        }
    }
}
void init()
{
    for(long long i=1;i<=n;i++)//一定要记得初始化！！
    {
        dis[i]=-1e9;
    }
}
int main()
{
    cin>>n>>m;
    init();//初始化
    for(long long i=1;i<=m;i++)//输入
    {
        long long u,v2,w;
        cin>>u>>v2>>w;
        v[u].push_back((uu){v2,w});
    }
    dijkstra();
    if(dis[n]==-1e9)
    {
        dis[n]=-1;
    }
    cout<<dis[n];
}