Submission #1285541


Source Code Expand

/*******************************************************************************
 * Copyright (c) 2016-2017, xehoth
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name xehoth, nor the names of its contributors may be used
 *       to endorse or promote products derived from this software without 
 *       specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY XEHOTH AND CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL XEHOTH AND CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 ******************************************************************************/
#include <bits/stdc++.h>
/**
 * 「AtCoder Beginner Contest 061」 13-05-2017
 * @author xehoth 
 */
namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template<class T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template<class T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() {
    fwrite(obuf, 1, oh - obuf, stdout);
}
}

namespace Task {

const int MAXN = 1010;

struct Node {
    int v;
    long long w;
    Node(int v, long long w) : v(v), w(w) {}
};

std::vector<Node> edge[MAXN];

inline void addEdge(const int u, const int v, const long long w) {
    edge[u].push_back(Node(v, w));
}

int num[MAXN], n;

long long dis[MAXN];

inline void spfa(int s) {
    static std::queue<int> q;
    static bool vis[MAXN];
    std::fill(dis, dis + n + 1, LLONG_MIN / 10);
    q.push(s), dis[s] = 0;
    register bool flag = false;
    register long long max = LLONG_MIN;
    register bool first = true;
    while (!q.empty()) {
        register int u = q.front();
        vis[u] = false, q.pop(), num[u]++;
        if (num[u] > n) {
            flag = true;
            break;
        }
        for (register int i = 0; i < edge[u].size(); i++) {
            Node *p = &edge[u][i];
            if (p->w + dis[u] > dis[p->v]) {
                dis[p->v] = p->w + dis[u];
                if (!vis[p->v]) {
                    if (p->v == n && first) {
                        max = dis[n], first = false;
                    }
                    q.push(p->v), vis[p->v] = true; 
                }
            }
        }
    }
    if (flag) {
        if (max == dis[n]) std::cout << dis[n] << "\n";
        else puts("inf");
        return;
    }
    std::cout << dis[n] << "\n";
}

inline void solve() {
    using namespace IO;
    register int m;
    read(n), read(m);
    register long long w;
    for (register int i = 0, u, v; i < m; i++) {
        read(u), read(v), read(w);
        addEdge(u, v, w);
    }
    spfa(1);
}
}

int main() {
#ifdef DBG
    freopen("in.in", "r", stdin);
#endif
    Task::solve();
    return 0;
}

Submission Info

Submission Time
Task D - Score Attack
User xehoth
Language C++14 (GCC 5.4.1)
Score 400
Code Size 4699 Byte
Status AC
Exec Time 24 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 14 ms 384 KB
subtask_1_13.txt AC 1 ms 256 KB
subtask_1_14.txt AC 9 ms 384 KB
subtask_1_15.txt AC 24 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 1 ms 384 KB
subtask_1_19.txt AC 1 ms 384 KB
subtask_1_2.txt AC 1 ms 384 KB
subtask_1_20.txt AC 1 ms 256 KB
subtask_1_21.txt AC 1 ms 384 KB
subtask_1_22.txt AC 1 ms 384 KB
subtask_1_23.txt AC 1 ms 256 KB
subtask_1_24.txt AC 1 ms 384 KB
subtask_1_25.txt AC 2 ms 256 KB
subtask_1_26.txt AC 1 ms 384 KB
subtask_1_27.txt AC 10 ms 384 KB
subtask_1_3.txt AC 1 ms 384 KB
subtask_1_4.txt AC 1 ms 384 KB
subtask_1_5.txt AC 4 ms 256 KB
subtask_1_6.txt AC 9 ms 384 KB
subtask_1_7.txt AC 1 ms 256 KB
subtask_1_8.txt AC 1 ms 384 KB
subtask_1_9.txt AC 1 ms 256 KB