QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719035#8760. 不等式zzisjtuWA 1ms3480kbC++231.7kb2024-11-06 22:10:272024-11-06 22:10:27

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 22:10:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3480kb
  • [2024-11-06 22:10:27]
  • 提交

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'