test/yukicoder/yuki_2712.test.cpp

View this file on GitHub
Last update: 2024-05-04 18:06:16+09:00
Problem: https://yukicoder.me/problems/no/2712

Depends on

Bellman-Ford Algorithm (ベルマン-フォード法) (lib/graph/bellman_ford.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/2712"
#include <bits/stdc++.h>
using namespace std;

#include "../../lib/graph/bellman_ford.hpp"

const long long INF = 0x1fffffffffffffff;

int main(){
    int n, m; cin >> n >> m;
    vector<long long> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    using T = tuple<long long, long long, long long>;
    vector<T> e;
    for(int i = 0; i < n; i++){
        e.emplace_back(i, i + n, -a[i]);
    }
    for(int i = 0; i < m; i++){
        long long a, b, c; cin >> a >> b >> c;
        a--, b--;
        e.emplace_back(a + n, b, c);
    }
    vector<long long> cost = bellman_ford(e, 2 * n, 0);
    if(cost[2 * n - 1] == -INF){
        cout << "inf" << "\n";
    }else{
        cout << -cost[2 * n - 1] << "\n";
    }
}

#line 1 "test/yukicoder/yuki_2712.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2712"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/graph/bellman_ford.hpp"

/**
 * @brief Bellman-Ford Algorithm (ベルマン-フォード法)
 * @docs docs/graph/bellman_ford.md
 */

template <typename T>
vector<long long> bellman_ford(const vector<T> &E, const int &n, const int &x){
    const long long INF = 0x1fffffffffffffff;
    vector<long long> cost(n, INF);
    cost[x] = 0;
    for(int i = 0; i < n - 1; i++){
        for(auto [from, to, t] : E){
            if(cost[from] == INF) continue;
            cost[to] = min(cost[to], cost[from] + t);
        }
    }
    for(int i = 0; i < n - 1; i++){
        for(auto [from, to, t] : E){
            if(cost[from] == INF) continue;
            if(cost[from] + t < cost[to]){
                cost[to] = -INF;
            }
        }
    }
    return cost;
}
#line 6 "test/yukicoder/yuki_2712.test.cpp"

const long long INF = 0x1fffffffffffffff;

int main(){
    int n, m; cin >> n >> m;
    vector<long long> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    using T = tuple<long long, long long, long long>;
    vector<T> e;
    for(int i = 0; i < n; i++){
        e.emplace_back(i, i + n, -a[i]);
    }
    for(int i = 0; i < m; i++){
        long long a, b, c; cin >> a >> b >> c;
        a--, b--;
        e.emplace_back(a + n, b, c);
    }
    vector<long long> cost = bellman_ford(e, 2 * n, 0);
    if(cost[2 * n - 1] == -INF){
        cout << "inf" << "\n";
    }else{
        cout << -cost[2 * n - 1] << "\n";
    }
}