// 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;
}
标签:dist,int,abc061d,st,cyc,include,LL
From: https://www.cnblogs.com/o2iginal/p/17502396.html