Submission #1284461


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <queue>

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;
struct Edge {
    int a, b, c;
    Edge (int a, int b, int c) : a(a), b(b), c(c) {}
    Edge () {}
};

int main () {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G;
    G.resize(N);
    vector<Edge> edges(M);

    REP (i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        G[b].push_back(a);
        edges[i].a = a;
        edges[i].b = b;
        edges[i].c = -c;
    }

    queue<int> q;
    vector<bool> isAccess(N, false);
    q.push(N - 1);
    while (q.size()) {
        int v = q.front();
        q.pop();
        if (isAccess[v]) continue;
        isAccess[v] = true;
        REP (i, 0, G[v].size()) {
            q.push(G[v][i]);
        }
    }

    const lli inf = 1LL << 60;
    vector<lli> dis(N, inf);
    dis[0] = 0;
    REP (i, 0, 2 * N) {
        for (auto edge : edges) {
            int from = edge.a;
            int to = edge.b;
            if (dis[from] + edge.c < dis[to]) {
                if (i >= N - 1 && (isAccess[to] || isAccess[from])) {
                    cout << "inf" << endl;
                    return 0;
                }
                dis[to] = dis[from] + edge.c;
            }
        }
    }
    cout << -dis[N - 1] << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Score Attack
User commy
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1534 Byte
Status
Exec Time 12 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
× 3
× 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 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask_1_1.txt 2 ms 256 KB
subtask_1_10.txt 1 ms 256 KB
subtask_1_11.txt 2 ms 256 KB
subtask_1_12.txt 6 ms 256 KB
subtask_1_13.txt 1 ms 256 KB
subtask_1_14.txt 4 ms 256 KB
subtask_1_15.txt 12 ms 384 KB
subtask_1_16.txt 1 ms 256 KB
subtask_1_17.txt 1 ms 256 KB
subtask_1_18.txt 4 ms 256 KB
subtask_1_19.txt 5 ms 384 KB
subtask_1_2.txt 4 ms 384 KB
subtask_1_20.txt 1 ms 256 KB
subtask_1_21.txt 4 ms 256 KB
subtask_1_22.txt 7 ms 384 KB
subtask_1_23.txt 1 ms 256 KB
subtask_1_24.txt 5 ms 256 KB
subtask_1_25.txt 3 ms 256 KB
subtask_1_26.txt 4 ms 256 KB
subtask_1_27.txt 7 ms 256 KB
subtask_1_3.txt 3 ms 256 KB
subtask_1_4.txt 4 ms 384 KB
subtask_1_5.txt 2 ms 256 KB
subtask_1_6.txt 4 ms 384 KB
subtask_1_7.txt 4 ms 256 KB
subtask_1_8.txt 4 ms 256 KB
subtask_1_9.txt 1 ms 256 KB