QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#325969 | #8136. Rebellious Edge | fryan | WA | 55ms | 3876kb | C++23 | 2.2kb | 2024-02-12 06:16:20 | 2024-02-13 03:05:13 |
Judging History
answer
#pragma GCC optimize("trapv")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
using namespace std;
#define int long long
#define P pair
#define pi P<int,int>
#define ff first
#define ss second
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vb V<bool>
#define v2b V<vb>
#define pb push_back
#define S set
#define si S<int>
#define ins insert
#define era erase
#define M map
#define mii M<int,int>
#define Q queue
#define PQ priority_queue
const int MOD=998244353;
const int INF=1e9;
int smax(int& a, int b) {return a = max(a,b);}
int smin(int& a, int b) {return a = min(a,b);}
struct PFX {
vector<int> pre;
PFX(vector<int>& arr) {
pre = vector<int>(arr.size()+1, 0);
for (int i = 1; i <= arr.size(); i++) {
pre[i] = pre[i-1] + arr[i-1];
}
}
int RSQ(int l, int r) {
if (l > r) return 0;
return pre[r+1]-pre[l];
}
};
int n, m, a, b, c;
V<vpi> adj;
V<vpi> rdj;
vi md;
void solve() {
adj.clear();
cin >> n >> m; adj = V<vpi>(n); rdj = V<vpi>(n); md = vi(n, INF);
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w; --u; --v;
if (u > v) {
a = v; b = u; c = w;
} else {
adj[u].pb(mp(v,w));
rdj[v].pb(mp(u,w));
smin(md[v],w);
}
}
vi afg(n, INF);
afg[0] = 0;
for (int i = 1; i < n; i++) {
afg[i] = md[i] + afg[i-1];
}
md[a] = 0;
PFX ad(md);
vi dp(n,INF); dp[0] = 0;
for (int i = 1; i <= b; i++) {
if (i == a) continue;
for (auto e : rdj[i]) {
if (e.ff == a) continue;
smin(dp[i],dp[e.ff] + e.ss + ad.RSQ(e.ff+1,i-1));
}
}
cout << min(afg[n-1],dp[b]+ad.RSQ(b+1,n-1)+c) << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
input:
3 5 6 1 2 4 1 3 2 2 3 0 3 4 1 4 5 1 5 2 1 4 4 1 2 4 1 3 6 1 4 8 4 2 1000000 3 3 1 2 100 2 1 10 2 3 1000
output:
5 18 1100
result:
ok 3 number(s): "5 18 1100"
Test #2:
score: -100
Wrong Answer
time: 55ms
memory: 3876kb
input:
50000 4 5 2 4 998973548 2 3 501271695 4 1 778395982 1 4 32454891 1 2 757288934 4 5 1 4 720856669 2 3 665098951 3 4 407461517 2 1 866914401 1 2 457859826 4 5 1 2 75288664 1 4 624893594 3 2 458973866 2 4 769074655 2 3 834773751 4 5 2 3 237060634 2 4 297307882 3 4 200383586 1 2 42856502 3 1 16574713 4 ...
output:
1291015520 1530420294 1534956009 480300722 1366795927 1541095843 1720144946 858095911 1034153425 793861088 605832428 1051598350 612891589 1265994009 517769091 1678219738 1556463491 93634961 960978736 984886788 1696503797 1002892611 1929526571 1263064938 1515267731 977157479 1937478556 654475526 1401...
result:
wrong answer 7th numbers differ - expected: '2493849488', found: '1720144946'