最长路

题目描述

给定一个有 N 个点的有向带权无环图，现求从 1 号点到 N 号点的最长路径。

---

输入

第一行有两个整数，分别代表图的点数 n 和边数 m。

第二到第 m+1 行，每行 33 个整数 u,v,w，代表存在一条从 u 到 v 边权为 w 的边。

输出

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

若 1 与 n 不联通，请输出 −1。

---

样例输入

3 4
1 3 10
1 2 5
1 2 4
2 3 7

样例输出

12

---

数据规模与约定

时间限制：1 s

内存限制：256 M

100% 的数据保证 2≤n≤1500,1≤m≤50000,−105≤w≤1052≤n≤1500,1≤m≤50000,−105≤w≤105

思路

• 初看第一眼题目加数据范围，不就是SPFA模板题吗，简单写了SPFA后，得了90分，后来发现由于负边的存在，dis数组得初始化为极小值
• 本题原本考察的是拓扑排序，就用拓扑排序写一下。

SPFA题解

#include <stdio.h>

#define MAX_M 50004

int n, m;
int cnt_edge, head[MAX_M], next[MAX_M], v[MAX_M], to[MAX_M];

inline void add_edge(int a, int b, int c) {
    to[++cnt_edge] = b;
    v[cnt_edge] = c;
    next[cnt_edge] = head[a];
    head[a] = cnt_edge;
    return ;
}


//int dfs(int *x, int *f) { //判断能否到达n点 
//    int tx = *x, tf = *f;
//    if (tx == n) return 1;
//    for (int i = head[tx]; i; i = next[i]) {
//        if (to[i] == tf) continue;
//        if (dfs(&to[i], &tx) == 1) return 1;
//    }
//    return 0;
//} 

#define MAX_N 1502

int dis[MAX_N], q[MAX_M], vis[MAX_N];

inline void SPFA() {
    
    for (int i = 1; i <= n; i++) dis[i] = -2000000000; //初始为极小值 
    dis[1] = 0;
    vis[1] = 1;
    q[0] = 1;
    int l = 0, r = 1;
    while (l < r) {
        int tp = q[l++];
        vis[tp] = 0;
        for (int i = head[tp]; i; i = next[i]) {
            if (dis[to[i]] >= dis[tp] + v[i]) continue;
            dis[to[i]] = dis[tp] + v[i];
            if (vis[to[i]]) continue;
            vis[to[i]] = 1;
            q[r++] = to[i];
        }
        
    }
    return ;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b ,c;
        scanf("%d %d %d", &a, &b, &c);
        add_edge(a, b, c);
    }
//    int x = 1, f = 0;
//    if (dfs(&x, &f) == 0) {
//        printf("-1\n");
//        return 0;
//    }
    SPFA();
    printf("%d\n", dis[n] == -2000000000 ? -1 : dis[n]);
    //注：使用SPFA不需要判断能否到达n点，只需初始化为极小值 
    return 0;
}

拓扑排序题解思路

• 首先提前判断1到n点是否连通，不连通直接输出-1；