Submission #1281249


Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;

#define int long long
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF (1LL<<60)
#define MOD 1000000007

int N, M;
vector<P> G[1001];
vector<P> R[1001];

int B[1001];
bool visited[1001];
void dfs(int x) {
  visited[x] = true;
  for (P p : R[x]) {
    if (!visited[p._1]) dfs(p._1);
  }
}

int f(int x, int d) {
  if (x == N) return d;
  if (B[x] >= d) return -INF;
  else {
    if (B[x] != -INF) return INF;
  }
  B[x] = d;
  int ret = -INF;
  for (P p : G[x]) {
    if (!visited[p._1]) continue;
    ret = max(ret, f(p._1, d+p._2));
  }
  return ret;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M;
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    G[a].pb(P(b, c));
    R[b].pb(P(a, c));
  }
  G[N-1].pb(P(N, 0));
  R[N].pb(P(N-1, 0));

  dfs(N);
  rep(i, N) B[i] = -INF;
  B[N] = 0;
  int m = f(0, 0);
  if (m == INF) cout << "inf\n";
  else cout << m << "\n";
  return 0;
}

Submission Info

Submission Time
Task D - Score Attack
User funcsr
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1362 Byte
Status AC
Exec Time 2 ms
Memory 512 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 384 KB
subtask_1_10.txt AC 1 ms 384 KB
subtask_1_11.txt AC 2 ms 384 KB
subtask_1_12.txt AC 2 ms 512 KB
subtask_1_13.txt AC 1 ms 256 KB
subtask_1_14.txt AC 2 ms 384 KB
subtask_1_15.txt AC 2 ms 512 KB
subtask_1_16.txt AC 1 ms 256 KB
subtask_1_17.txt AC 1 ms 384 KB
subtask_1_18.txt AC 2 ms 384 KB
subtask_1_19.txt AC 2 ms 512 KB
subtask_1_2.txt AC 2 ms 384 KB
subtask_1_20.txt AC 1 ms 256 KB
subtask_1_21.txt AC 2 ms 384 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 384 KB
subtask_1_26.txt AC 2 ms 384 KB
subtask_1_27.txt AC 2 ms 384 KB
subtask_1_3.txt AC 2 ms 384 KB
subtask_1_4.txt AC 2 ms 384 KB
subtask_1_5.txt AC 2 ms 384 KB
subtask_1_6.txt AC 2 ms 384 KB
subtask_1_7.txt AC 2 ms 384 KB
subtask_1_8.txt AC 2 ms 384 KB
subtask_1_9.txt AC 1 ms 256 KB