ABC061 D Score Attack

using namespace std;
//const ll MOD=(ll)1e9+7;
const ll inf=(ll)1e15;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
ll d[1001];
vector<pair<int,ll> > v[1001];
bool used[1001];

void dfs(int now){
  used[now]=1;
  for(int i=0;i<(int)v[now].size();i++){
    if(!used[v[now][i].fi])dfs(v[now][i].fi);
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int from,to;
    ll cost;
    cin>>from>>to>>cost;
    from--;to--;
    v[from].push_back({to,-cost});
  }
  for(int i=0;i<n;i++){
    d[i]=inf;
  }
  d[0]=0;
  ll temp=0;
  for(int i=0;i<=m+10;i++){
    for(int j=0;j<n;j++){
      int now=j;
      if(d[now]==inf)continue;
      for(int k=0;k<(int)v[now].size();k++){
        if(d[now]+v[now][k].se>=d[v[now][k].fi])continue;
        d[v[now][k].fi]=d[now]+v[now][k].se;
      }
    }
    if(i==m)temp=d[n-1];
  }
  bool circle=0;
  if(temp!=d[n-1])circle=1;
  if(circle){
    print("inf");
  }else{
    print(-d[n-1]);
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

• 閉路があるだけじゃあ得点を無限に増やせる理由にならないことに気づきたい。
• これは多めにベルマンフォードで回して、ゴールの距離が更に近づいたかどうかで判定ができる。