QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719035 | #8760. 不等式 | zzisjtu | WA | 1ms | 3480kb | C++23 | 1.7kb | 2024-11-06 22:10:27 | 2024-11-06 22:10:27 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
#define lowbit(i) ((i)&(-i))
#define pii pair<int,int>
#define endl '\n'
#define mk(x,y) make_pair(x,y)
#define popcount(x) __builtin_popcount(x)
#define LF(x) fixed<<setprecision(x)
const double pi = 3.14159265358979323846;
const double eps = 1e-9;
const int inf = 1e9;
const long long INF = 4e18;
const int mod = 1e9+7;
using namespace std;
const int N = 2e5+10;
struct edge {
int v, w;
};
vector<edge> e[N];
void solve() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
e[b].push_back({a, -c});
}
for(int i = 1; i <= n; i++) {
e[0].push_back({i, 0});
}
vector<int> dis(n + 1, inf), cnt(n + 1);
auto spfa = [&](int s) {
queue<int> q;
q.push(s);
vector<int> vis(n + 1, false);
dis[s] = 0;
vis[s] = 1;
while(q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for(auto [v, w]: e[u]) {
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if(!vis[v]) {
q.push(v);
cnt[v]++;
if(cnt[v] >= n + 1)return false;
vis[v] = 1;
}
}
}
}
return true;
};
if(spfa(0)) {
int ans = 0;
for(int i = 1; i <= n; i++) {
ans += abs(dis[i]);
}
if(ans > 1e9)ans = -1;
cout << ans << endl;
}
else cout << -1 << endl;
}
#undef int
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3480kb
input:
3 1 1 2 2
output:
2
result:
wrong answer 1st numbers differ - expected: '4', found: '2'