526互联

abc061d <单源最短路, spfa, 判断负环>

发布时间 2023-06-25 10:53:27作者: O2iginal

D - Score Attack

// https://atcoder.jp/contests/abc061/tasks/abc061_d
// 单源最短(长)路, spfa, 判断负(正)环
// 本题是找最长的路径, 实际上取个负号即可
// 注意, 找到一个负环不能直接结束, 只能进行标记 cyc[]
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 1010;
const LL INF = 1e15;
int cnt[N]; // 用于判断正环
bool st[N]; // i 是否在队列中
bool cyc[N];  // 判断是否成环
LL dist[N]; // 1~i 最长路
int n, m;

struct Edge {int v; LL w;};
vector<Edge> adj[N];


bool spfa()
{
    for (int i = 2; i <= n; i++) dist[i] = -INF; // dist[1] = 0;
    queue<int> q;
    q.push(1); st[1] = true;
    while (q.size())
    {
        int u = q.front(); q.pop(); st[u] = false;
        for (auto e: adj[u])
        {
            int v = e.v; LL w = e.w;
            if (cyc[v]) continue;
            if (dist[u] + w > dist[v])
            {
                cnt[v] = cnt[u] + 1; // 累计更新次数, 判断是否存在正环
                if (cnt[v] >= n) cyc[v] = true;  // 这里不能直接返回,  因为找到正环并不代表dist[n-1]在
                dist[v] = dist[u] + w;
                if (!st[v])
                {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }
    return cyc[n];
}

void solv()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }
    if (spfa())
        cout << "inf" << endl;
    else
        cout << dist[n] << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solv();
    }
    return 0;
}