P1938 [USACO09NOV] Job Hunt S

//最短路性质：所有的最短路可以合并成DAG(有向无环图)
//跑最长路，若不含正环则可以直接运行不会陷入死循环
//若包含正环，则最坏情况下贡献为1的正环有220个点(-1*219+200)
//由于这里若能得出答案可知走出的最长路为DAG,则最多走过151个点，最大贡献为151000,若超出151000说明有正环，答案为-1
//总时长为151000*220<1e8,可以通过
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
vector<pii> to[100001];
int dis[220];
int D, m1, n, m2, s;
int main() {
    scanf("%d%d%d%d%d", &D, &m1, &n, &m2, &s);
    int ans = D;
    for (int i = 1; i <= m1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        to[u].push_back({D, v});
    }
    for (int i = 1; i <= m2; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        to[u].push_back({D - w, v});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [pre, u] = pq.top();
        pq.pop();
        if (pre < dis[u])
            continue;
        for (auto [cst, v] : to[u]) {
            if (pre + cst > dis[v]) {
                dis[v] = pre + cst;
                ans = max(ans, dis[v]+D);
                if(ans>150000){
                    printf("-1");
                    return 0;
                }
                pq.push({pre + cst, v});
            }
        }
    }
    printf("%d", ans);
}