Submission #1281489

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

using namespace std;

#define MAX_N 1005

#define int long long

int N;
int M;

using II = pair<LL, LL>;

vector<II> Edge[MAX_N];

class edge{
public:
  int from, to, cost;
};

vector<edge> EdgeVec;

bool used[MAX_N];
LL score[MAX_N];

LL d[MAX_N];

bool find_loop()
{
  memset(d, 0, sizeof(d));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < EdgeVec.size(); j++) {
      edge e = EdgeVec[j];
      if(d[e.to] > d[e.from] - e.cost){
        d[e.to] = d[e.from] - e.cost;

        if(i == N-1) return true;
      }
    }
  }

  return false;
}

void solve()
{

  if(find_loop()){
    cout << "inf" << endl;
    return;
  }

  priority_queue<II> que;
  que.push(II(0, 0));

  for (int i = 0; i < MAX_N; i++) {
    score[i] = -INF_LL_MAX;
  }

  while(que.size()){
    II p = que.top();
    que.pop();

    int pos = p.second, cost = p.first;
    if(score[pos] > cost){
      continue;
    }

    for (int i = 0; i < Edge[pos].size(); i++) {
      if(score[Edge[pos][i].first] < cost + Edge[pos][i].second){
        score[Edge[pos][i].first] = cost + Edge[pos][i].second;
        que.push(II(score[Edge[pos][i].first], Edge[pos][i].first));
      }
    }

  }

  cout << score[N-1] << endl;
}

signed main()
{
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int A, B; LL C;
    cin >> A >> B >> C;
    A--; B--;
    Edge[A].push_back(II(B, C));
    edge e; e.from = A, e.to = B; e.cost = C;
    EdgeVec.push_back(e);
  }

  solve();

  return 0;
}

Submission Info

Judge Result