Submission #2549667

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >

vector< T > shortest_path_faster_algorithm(WeightedGraph< T > &g, int s) {
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(g.size(), INF);
  vector< int > pending(g.size(), 0), times(g.size(), 0);
  queue< int > que;

  que.emplace(s);
  pending[s] = true;
  ++times[s];
  dist[s] = 0;

  while(!que.empty()) {
    int p = que.front();
    que.pop();
    pending[p] = false;
    for(auto &e : g[p]) {
      T next_cost = dist[p] + e.cost;
      if(next_cost >= dist[e.to]) continue;
      dist[e.to] = next_cost;
      if(!pending[e.to]) {
        if(++times[e.to] >= g.size()) return vector< T >();
        pending[e.to] = true;
        que.emplace(e.to);
      }
    }
  }
  return dist;
}


int main() {
  int N, M;
  int P[1000], Q[1000];

  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%d", &P[i]);
  }
  for(int i = 0; i < N; i++) {
    scanf("%d", &Q[i]);
  }
  WeightedGraph< int > g(2 * N + 1);
  int S = 2 * N;
  for(int i = 0; i < N; i++) {
    g[i].emplace_back(S, 0);
    g[S].emplace_back(i, P[i]);
    g[S].emplace_back(N + i, 0);
    g[N + i].emplace_back(S, Q[i]);
  }
  for(int i = 0; i < M; i++) {
    int x, y, a, b;
    scanf("%d %d %d %d", &x, &y, &a, &b);
    --x, --y;
    g[x].emplace_back(N + y, -a);
    g[N + y].emplace_back(x, b);
  }
  auto ret = shortest_path_faster_algorithm(g, S);
  if(ret.empty() || ret[S] < 0) puts("no");
  else puts("yes");
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
                         ^
./Main.cpp:68:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &P[i]);
                       ^
./Main.cpp:71:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q[i]);
                       ^
./Main.cpp:83:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &x, &y, &a, &b);
                                         ^

Judge Result