Submission #2125589


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,m;
  cin>>n>>m;
  vi a(m),b(m),c(m);
  rep(i,m){
    cin>>a[i]>>b[i]>>c[i];
    a[i]--;
    b[i]--;
    c[i]*=-1;
  }

  vector<ll> d(n,(ll)INF*INF);
  d[0]=0;
  rep(i,n-1)rep(j,m)
    d[b[j]] = min(d[b[j]], d[a[j]] + c[j]);
 
  vector<bool> negative(n,false);
  
  rep(i,n)rep(j,m){
    if(negative[a[j]])
      negative[b[j]] = true;
    if(d[b[j]] > d[a[j]] + c[j]){
      d[b[j]] = d[a[j]] + c[j];
      negative[b[j]] = true;
    }
  }
  if(negative[n-1])
    cout<<"inf"<<endl;
  else
    cout<<-d[n-1]<<endl;
}

Submission Info

Submission Time
Task D - Score Attack
User rika0384
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1255 Byte
Status
Exec Time 13 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 400 / 400 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 8 ms 256 KB
subtask_1_13.txt 1 ms 256 KB
subtask_1_14.txt 9 ms 256 KB
subtask_1_15.txt 13 ms 256 KB
subtask_1_16.txt 1 ms 256 KB
subtask_1_17.txt 1 ms 256 KB
subtask_1_18.txt 5 ms 256 KB
subtask_1_19.txt 8 ms 256 KB
subtask_1_2.txt 7 ms 256 KB
subtask_1_20.txt 1 ms 256 KB
subtask_1_21.txt 6 ms 256 KB
subtask_1_22.txt 10 ms 256 KB
subtask_1_23.txt 1 ms 256 KB
subtask_1_24.txt 7 ms 256 KB
subtask_1_25.txt 3 ms 256 KB
subtask_1_26.txt 7 ms 256 KB
subtask_1_27.txt 9 ms 256 KB
subtask_1_3.txt 5 ms 256 KB
subtask_1_4.txt 7 ms 256 KB
subtask_1_5.txt 4 ms 256 KB
subtask_1_6.txt 9 ms 256 KB
subtask_1_7.txt 6 ms 256 KB
subtask_1_8.txt 7 ms 256 KB
subtask_1_9.txt 1 ms 256 KB