//最短路性质:所有的最短路可以合并成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); }