View Code of Problem 3933

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000;
const int MAXM = 200000;

struct Graph {
    struct Edge {
        int to, next;
        int cost;
    } edge[MAXM];
    int head[MAXN];
    int tot;

    void init(int n) {
        tot = 0;
        memset(head, -1, sizeof(int) * (n + 1));
    }

    void add_edge(int from, int to, int value) {
        edge[tot].to = to;
        edge[tot].cost = value;
        edge[tot].next = head[from];
        head[from] = tot++;
    }
};

struct SPFA {
    bool visited[MAXN];    //标记数组
    int dist[MAXN];        //源点到顶点i的最短距离
    int path[MAXN];        //记录最短路的路径
    int enqueue_num[MAXN]; //记录入队次数

    bool solve(int b, int e, int start, const Graph &graph) {
        for (int i = b; i < e; i++) {
            visited[i] = false;
            enqueue_num[i] = 0;
            dist[i] = INT_MAX;
            path[i] = start;
        }
        queue<int> Q;
        Q.push(start);
        dist[start] = 0;
        visited[start] = true;
        enqueue_num[start]++;
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            visited[u] = 0;
            for (int v = graph.head[u]; v != -1; v = graph.edge[v].next) {
                int to = graph.edge[v].to;
                if (dist[u] + graph.edge[v].cost < dist[to]) {
                    dist[to] = dist[u] + graph.edge[v].cost;
                    path[v] = u;
                    if (!visited[to]) {
                        Q.push(to);
                        enqueue_num[to]++;
                        if (enqueue_num[to] >= e)
                            return false;
                        visited[to] = 1;
                    }
                }
            }
        }
        return true;
    }
};

Graph graph;
SPFA spfa;

void solve() {
    int n, m, l, u;
    while (cin >> n >> m >> l >> u) {
        graph.init(n + m + 100);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int tmp;
                cin >> tmp;
                graph.add_edge(i, j + n, log10(1.0 * tmp / l));
                graph.add_edge(j + n, i, log10(1.0 * u / tmp));
            }
        }
        if (spfa.solve(1, n + m, 1, graph)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed localTestCount = 1, localReadPos = cin.tellg();
    char localTryReadChar;
    do {
        if (localTestCount > 20)
            throw runtime_error("Check the stdin!!!");
        auto startClockForDebug = clock();
        solve();
        auto endClockForDebug = clock();
        cout << "Test " << localTestCount << " successful" << endl;
        cerr << "Test " << localTestCount++ << " Run Time: "
             << double(endClockForDebug - startClockForDebug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (localReadPos != cin.tellg() && cin >> localTryReadChar && localTryReadChar != '$' &&
             cin.putback(localTryReadChar));
#else
    solve();
#endif
    return 0;
}