Submission #1285613

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cctype>
#include <ctime>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define eps 1e-9

typedef long long ll;
typedef pair<int, int> pii;

const ll INF = 1e18;
const int maxn = 2e3 + 10;
int n, m, a, b, c, edge = 0;
int head[maxn], Next[maxn], to[maxn], cnt[maxn];
ll val[maxn], dis[maxn];
bool vis[maxn], vis1[maxn];
bool flag;

inline void add_edge(int u, int v, int _val) {
    to[edge] = v; val[edge] = _val; Next[edge] = head[u]; head[u] = edge++;
}
void dfs(int u) {
    if (u == n) { flag = true; return; }
    for (int i = head[u]; i != -1; i = Next[i]) {
        if (vis1[to[i]]) { continue; } vis1[to[i]] = true; dfs(to[i]);
    }
}
bool judge(int u) { memset(vis1, false, sizeof(vis1)); flag = false; dfs(u); return flag; }

bool spfa() {
    memset(vis, false, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); int f;
    dis[1] = 0; for (int i = 2; i <= n; ++i) { dis[i] = INF; }
    queue<int> q; q.push(1);
    while (!q.empty()) {
        f = q.front(); q.pop(); vis[f] = false; ++cnt[f];
        if (cnt[f] > n + 1) {
            if (judge(f)) { return false; } vis[f] = true;
        }
        for (int i = head[f]; i != -1; i = Next[i]) {
            if (dis[to[i]] > dis[f] + val[i]) {
                dis[to[i]] = dis[f] + val[i];
                if (!vis[to[i]]) { vis[to[i]] = true; q.push(to[i]); }
            }
        }
    }
    return true;
}
int main() {
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif // __AiR_H
    memset(head, -1, sizeof(head));
    scanf("%d %d", &n, &m);
    while (m--) {
        scanf("%d %d %d", &a, &b, &c); c = -c; add_edge(a, b, c);
    }
    if (spfa()) { printf("%lld\n", -dis[n]); } else { printf("inf\n"); }
#ifdef __AiR_H
    printf("Time used = %.2fs\n", (double)clock() / CLOCKS_PER_SEC);
#endif // __AiR_H
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
                           ^
./Main.cpp:68:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c); c = -c; add_edge(a, b, c);
                                      ^

Judge Result