样例wa求助
查看原帖
样例wa求助
1004463
RaymondOccam楼主2025/1/18 15:43

原谅太蒻

#include <iostream>
#include <vector>
#include <queue>
#define LL long long
const LL maxn = 1005;
struct Edge {
  LL to, w;
};
LL n, ml, md, a, b, d;
LL dis[maxn], cnt[maxn];
bool vis[maxn];
std::vector <Edge> G[maxn];
std::queue <LL> q;
bool spfa (LL s) {
  q.push (s);
  vis[s] = 1, dis[s] = 0;
  while (!q.empty ()) {
    LL u = q.front ();
    q.pop ();
    vis[u] = 0;
    for (LL i = 0; i < (LL) G[u].size (); i++) {
      LL v = G[u][i].to, w = G[u][i].w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) {
          vis[v] = 1, cnt[v]++;
          if (cnt[v] >= n) {
            return 1;
          }
          q.push (v);
        }
      }
    }
  }
  return 0;
}
int main () {
  std::cin.tie (0) -> sync_with_stdio (false);
  std::cin >> n >> ml >> md;
  dis[1] = 1e13;
  for (LL i = 2; i <= n; i++) {
    G[i - 1].push_back ({i, 0});
    dis[i] = 1e13;
  }
  for (LL i = 1; i <= ml; i++) {
    std::cin >> a >> b >> d;
    G[a].push_back ({b, d});
  }
  for (LL i = 1; i <= md; i++) {
    std::cin >> a >> b >> d;
    G[b].push_back ({a, -d});
  }
  for (LL i = n; i >= 1; i--) {
    if (!vis[i]) {
      if (spfa (i) == 1) {
        std::cout << -1;
        return 0;
      }
    }
  }
  if (dis[n] >= 1e13) {
    std::cout << -2;
  } else {
    std::cout << dis[n];
  }
  return 0;
}
2025/1/18 15:43
加载中...