55

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp[1005];
        for (int i = 0; i < nums.size(); i++) dp[i + 1] = max(dp[i], 0) + nums[i];
        return *max_element(dp + 1, dp + nums.size() + 1);
    }
};

1627

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

int n, m, a[10005], b[10005], k, vis[10005];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i] >> b[i];
    cin >> k;
    while (k--) {
        memset(vis, 0, sizeof vis);
        int x, fl = 1;
        cin >> x;
        for (int i = 1; i <= x; i++) {
            int y;
            cin >> y;
            vis[y] = 1;
        }
        for (int i = 1; i <= m; i++)
            if (!vis[a[i]] && !vis[b[i]])
                fl = 0;
        if (fl) puts("Yes");
        else puts("No");
    }
    return 0;
}

341

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

const int N = 5e5 + 5, M = 1e5 + 5;
int a[M];
vector<int> f[N], g[N];
int n, m, dis[M], res;
bool fromn[M];

void dfs(int u) {
    if (fromn[u]) return;
    fromn[u] = 1;
    for (auto v : f[u]) dfs(v);
}

void spfa() {
    queue<int> q;
    q.push(1);
    memset(dis, 0x3f, sizeof dis);
    dis[1] = a[1];
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : g[u])
            if (dis[v] > min(dis[u], a[v])) {
                dis[v] = min(dis[u], a[v]);
                q.push(v);
            }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--) {
        int op, x, y;
        cin >> x >> y >> op;
        if (op == 2) {
            f[x].push_back(y);
            f[y].push_back(x);
            g[x].push_back(y);
            g[y].push_back(x);
        } else {
            g[x].push_back(y);
            f[y].push_back(x);
        }
    }
    dfs(n);
    spfa();
    for (int i = 1; i <= n; i++)
        if (fromn[i])
            res = max(res, a[i] - dis[i]);
    cout << res;
    return 0;
}