Submission #3609409

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;

const ll MAX_V = 2 * 1e3 + 1;
const ll MAX_E = 4 * 1e3 + 2 * 1e5;

struct edge {
	ll from, to, cost;
};
ll d[MAX_V];
ll V, E;

edge es[MAX_E];

void shortest_path(int s) {
	rep(i, 0, V) d[i] = INF;
	d[s] = 0;
	while(true) {
		bool update = false;
		rep(i, 0, E) {
			edge e = es[i];
			if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if(!update) break;
	}
}

bool find_negative_loop(int s) {
	//memset(d, 0, sizeof(d));
	fill(d, d + V, INF);
	d[s] = 0;
	rep(i, 0, V) {
		rep(j, 0, E) {
			edge e = es[j];
			if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				if(i == V - 1) return true;
			}
		}
	}
	return false;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll N, M;
	cin >> N >> M;
	ll p[N], q[N], x[M], y[M], a[M], b[M];
	rep(i, 0, N) cin >> p[i];
	rep(i, 0, N) cin >> q[i];
	rep(i, 0, M) cin >> x[i] >> y[i] >> a[i] >> b[i];

	V = 0; E = 0;
	rep(i, 0, N) {
		es[E].from = 2 * N;
		es[E].to = i;
		es[E].cost = p[i];
		E++;
		es[E].from = i;
		es[E].to = 2 * N;
		es[E].cost = 0;
		E++;
	}

	rep(i, 0, N) {
		es[E].from = 2 * N;
		es[E].to = N + i;
		es[E].cost = 0;
		E++;
		es[E].from = N + i;
		es[E].to = 2 * N;
		es[E].cost = q[i];
		E++;
	}

	rep(i, 0, M) {
		es[E].from = N + y[i] - 1;
		es[E].to = x[i] - 1;
		es[E].cost = b[i];
		E++;
		es[E].from = x[i] - 1;
		es[E].to = N + y[i] - 1;
		es[E].cost = -a[i];
		E++;
	}
	V = 2 * N + 1;

	if(find_negative_loop(0)) {
		cout << "no" << endl;
		return 0;
	}
	cout << "yes" << endl;

}

Submission Info

Judge Result