Submission #1282514


Source Code Expand

#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

// 頂点は0-originとする
template <typename T>
class BellmanFord {
    struct edge {
        int from;
        int to;
        T cost;
    };

public:
    T INF;
    T NEGATIVE_INF;

    BellmanFord(int V)
        : INF(std::numeric_limits<T>::max())
        , NEGATIVE_INF(std::numeric_limits<T>::min())
        , m_V(V) {
        m_es.clear();
    }

    void add_dir_edge(int from, int to, T cost) {
        m_es.push_back( edge{from, to, cost} );
    }

    void add_undir_twoways(int v1, int v2, T cost) {
        add_dir_edge(v1, v2, cost);
        add_dir_edge(v2, v1, cost);
    }

    // 頂点sから各頂点までの距離を計算してdに格納
    vector<T> shortest_path(int s)
    {
        // INF: その頂点には到達できない
        // INF以外: sからの最短距離
        vector<T> d(m_V, INF);
        vector<char> has_negative_loop(m_V);
        d[s] = 0;
        REP(try_num, m_V) {
            bool update = false;
            REP(i, SIZE(m_es)) {
                edge e = m_es[i];
                if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                    d[e.to] = d[e.from] + e.cost;
                    update = true;

                    // 無限ループ発見
                    if (try_num == m_V - 1) {
                        has_negative_loop[e.to] = 1;
                    }
                }
            }
            if (!update) break;
        }

        // cout << "dists:" << endl;
        // for (auto e: d) cout << e << " ";
        // cout << endl;
        // cout << "negative loop:" << endl;
        // for (auto e: has_negative_loop) cout << int(e) << " ";
        // cout << endl;

        // negative loopがある頂点の最短路をNEGATIVE_INFに書き換える
        REP(i, m_V) {
            if (has_negative_loop[i]) d[i] = NEGATIVE_INF;
        }

        return move(d);
    }

    // sから各頂点までの最短路に閉路があるかを返す
    bool find_negative_loop_from_v(int s) {
        vector<T> d(m_V, INF);
        
        d[s] = 0;
        // ループの実行は高々|V|-1回のはず
        // ループの実行回数が|V|よりも大きければ閉路があったとみなす
        int count = 0;
        while (true) {
            bool update = false;
            REP(i, SIZE(m_es)) {
                edge e = m_es[i];
                if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                    d[e.to] = d[e.from] + e.cost;
                    update = true;
                }
            }
            if (!update) break;

            ++count;
            if (count > m_V) return true;
        }

        return false;
    }

    // グラフ全体のどこかに負の経路があることを検出
    bool find_negative_loop_somewhere(void) {
        vector<T> d(m_V);

        REP(i, SIZE(d)) {
            REP(j, SIZE(m_es)) {
                edge e = m_es[j];
                if (d[e.to] > d[e.from] + e.cost){
                    d[e.to] = d[e.from] + e.cost;
                    // n回目にも更新があるなら負の経路が存在する
                    if (i == SIZE(d) - 1) {
                        return true;
                    }
                }
            }

            // for(int i = 0; i < SIZE(d); ++i) {
            //     cout << d[i] << ", ";
            // }
            // cout << endl;
        }
        return false;
    }

private:
    int m_V;                   
    vector<edge> m_es;
};

int main(void)
{
    cin.sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    BellmanFord<ll> bf(N);
    REP(m, M) {
        ll a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        bf.add_dir_edge(a, b, -c);
    }

    auto dists = bf.shortest_path(0);
    if (dists[N-1] == bf.NEGATIVE_INF) {
        cout << "inf" << endl;
    }
    else {
        cout << -dists[N-1] << endl;
    }

    return 0;
}

Submission Info

Submission Time
Task D - Score Attack
User minus9d
Language C++14 (GCC 5.4.1)
Score 400
Code Size 4719 Byte
Status AC
Exec Time 5 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_1.txt AC 1 ms 256 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 2 ms 256 KB
subtask_1_12.txt AC 3 ms 384 KB
subtask_1_13.txt AC 1 ms 256 KB
subtask_1_14.txt AC 3 ms 256 KB
subtask_1_15.txt AC 5 ms 384 KB
subtask_1_16.txt AC 1 ms 256 KB
subtask_1_17.txt AC 1 ms 256 KB
subtask_1_18.txt AC 2 ms 256 KB
subtask_1_19.txt AC 2 ms 384 KB
subtask_1_2.txt AC 1 ms 256 KB
subtask_1_20.txt AC 1 ms 256 KB
subtask_1_21.txt AC 1 ms 256 KB
subtask_1_22.txt AC 2 ms 384 KB
subtask_1_23.txt AC 1 ms 256 KB
subtask_1_24.txt AC 2 ms 384 KB
subtask_1_25.txt AC 2 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 4 ms 256 KB
subtask_1_3.txt AC 1 ms 256 KB
subtask_1_4.txt AC 1 ms 256 KB
subtask_1_5.txt AC 2 ms 256 KB
subtask_1_6.txt AC 4 ms 256 KB
subtask_1_7.txt AC 1 ms 256 KB
subtask_1_8.txt AC 1 ms 256 KB
subtask_1_9.txt AC 1 ms 256 KB