比赛 |
4043级NOIP2022欢乐赛2nd |
评测结果 |
AWAAAWAAAA |
题目名称 |
奶牛排队 |
最终得分 |
80 |
用户昵称 |
lihaoze |
运行时间 |
0.724 s |
代码语言 |
C++ |
内存使用 |
0.60 MiB |
提交时间 |
2022-10-31 19:09:57 |
显示代码纯文本
#include "bits/stdc++.h"
const int N = 10010;
int n, l, d, dist[N], st[N], cnt[N];
int e[N], ne[N], h[N], w[N], idx;
void add(int a, int b, int x) {
e[idx] = b, ne[idx] = h[a], w[idx] = x, h[a] = idx ++;
}
void spfa() {
memset(dist, 0x3f, sizeof dist);
std::queue<int> q;
q.push(1), dist[1] = 0, st[1] = true, cnt[1] = 1;
while (q.size()) {
int u = q.front(); q.pop();
st[u] = false;
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (dist[v] > dist[u] + w[i]) {
dist[v] = dist[u] + w[i];
if (!st[v]) {
++ cnt[v];
q.push(v), st[v] = true;
}
}
}
}
}
int main() {
freopen("layout.in", "r", stdin);
freopen("layout.out", "w", stdout);
memset(h, -1, sizeof h);
std::cin >> n >> l >> d;
for (int i = 1; i <= l; ++ i) {
int x, y, w;
std::cin >> x >> y >> w;
add(x, y, w);
}
for (int i = 1; i <= d; ++ i) {
int x, y, w;
std::cin >> x >> y >> w;
add(y, x, -w);
}
spfa();
for (int i = 1; i <= n; ++ i) {
if (cnt[i] > n) {
return std::cout << -2 << '\n', 0;
}
}
if (dist[n] == 0x3f3f3f3f) {
std::cout << -1 << '\n';
} else {
std::cout << dist[n] << '\n';
}
return 0;
}
// d_a - d_b >= l => d_a >= l + d_b
// d_a - d_b <= l => d_b >= -l + d_a