G 为有 n 个顶点的带权有向无环图,G 中各顶点的编号为 1n,请设计算法,计算图 G1n 间的最长路径。

输入格式

输入的第一行有两个整数,分别代表图的点数 n 和边数 m

接下来的 m 行,每行包含三个整数 u, v, wu < v),代表存在一条从 uv 边权为 w 的边。

输出格式

输出一行一个整数,代表 1n 的最长路。

1 无法到达 n,请输出 -1

输入样例

2 1
1 2 1

输出样例

1

说明

对于 2 对于 4 对于 10

代码实现

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 5e4 + 10;

int n, m, idx, h[N], e[N], w[N], ne[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa() {
    int dist[N], st[N];
    queue <int> que;
    memset(dist, -1, sizeof dist), memset(st, 0, sizeof st);
    dist[1] = 0;
    st[1] = 1;
    que.push(1);
    while(que.size()) {
        auto t = que.front(); que.pop();
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    st[j] = 1;
                    que.push(j);
                }
            }
        }
    }
    return dist[n];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << spfa();
    return 0;
} 
分类: SPFA

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status