Submission #33603896

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

ll dp[2][200010];
ll mx[200010]; // 只记录1的, 因为0的直接记录在pq和dp中, 而1的在子节点未完全计算时pq和dp都不会记录
int deg[200010]; // 正向图出度, 反向图入度
vector<pair<int,int> > g[200010]; // 反向图 v = {u, weight}

template <typename T>
using minPQ = priority_queue<T,vector<T>, greater<T>>; // 小根堆

int main(){
  int n = read();
  int m = read();
  int v = read();// 起点
  rep(i,0,2) fill(dp[i],dp[i]+n+1,-1); // 未访问
  rep(i,0,m) {
    int u = read();
    int v = read();
    int w = read();
    g[v].push_back({u, w});
    deg[u] ++;
  }
  minPQ<array<ll,3>> q; // 小根堆, dij 每次找最小的未达点变为可达 {距离, 0/1, 点}
  rep(i,1,n+1) if(deg[i] == 0) rep(j,0,2) q.push({0, j, i}); // dp[0/1][i] 反向入度为0 的节点
  while(q.size()) {
    auto [d, i, u] = q.top(); q.pop();
    if(dp[i][u] != -1) continue; // 计算过
    dp[i][u] = d; // 更新值
    if(!i) { // dp[0][u] -> dp[1][v]
      for(auto [v, w] : g[u]) { // 更新反向边 并更新 deg[v] --
        mx[v] = max(mx[v], d + w); // 更新值但是 不一定进入pq dp[x][1] = max (f[y][0] + weight[x][y])
        if(--deg[v] == 0) q.push({mx[v], 1, v}); // dp[1][v] 只能所有计算都计算后才有意义
      }
    } else for(auto [v, w] : g[u]) q.push({d + w, 0, v}); // dp[1][u] -> dp[0][v] dij
  }
  if(dp[0][v] == -1) printf("INFINITY\n");
  else printf("%lld\n", dp[0][v]);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:7:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    7 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result