QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352049 | #7185. Poor Students | installb | TL | 1ms | 3880kb | C++17 | 2.7kb | 2024-03-12 20:00:17 | 2024-03-12 20:00:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
ll dis[25];
int inq[25],pre[25],prv[25];
set <pair <int,int> > st[25][25];
int c[100005][25],dir[25][100005],deg[25],n,k;
int spfa(){
for(int i = 0;i <= k;i ++){
dis[i] = LLINF; inq[i] = 0;
}
queue <int> q; q.push(0);
inq[0] = 1; dis[0] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
inq[u] = 0;
for(int v = 0;v <= k;v ++){
if(st[u][v].size()){
auto [w,id] = *st[u][v].begin();
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
prv[v] = u; pre[v] = id;
if(!inq[v]){
inq[v] = 1;
q.push(v);
}
}
}
}
}
int id = -1;
for(int i = 1;i <= k;i ++){
if(deg[i] > 0 && (id == -1 || dis[i] < dis[id])) id = i;
}
return id;
}
void solve(){
cin >> n >> k;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= k;j ++){
cin >> c[i][j];
}
c[i][0] = INF;
}
for(int i = 1;i <= k;i ++) cin >> deg[i];
for(int i = 1;i <= n;i ++){
dir[0][i] = 1;
for(int j = 1;j <= k;j ++){
st[0][j].insert({c[i][j] - c[i][0],i});
}
}
ll ans = 0;
for(int ti = 1;ti <= n;ti ++){
// for(int i = 0;i <= k;i ++){
// for(int j = 0;j <= k;j ++){
// if(st[i][j].size()) cout << st[i][j].begin()->first << ',' << st[i][j].begin()->second << ' ';
// else cout << "0,0 ";
// }
// cout << endl;
// }
int v = spfa();
deg[v] --;
ans += dis[v];
for(int i = 1;i <= k;i ++) assert(deg[i] >= 0);
while(v){
int u = prv[v],w = pre[v];
// u -> w -> v
for(int i = 0;i <= k;i ++){
if(i != u){
if(!dir[i][w]) st[u][i].erase({c[w][i] - c[w][u],w});
else st[i][u].insert({c[w][u] - c[w][i],w});
}
}
for(int i = 0;i <= k;i ++){
if(i != v){
if(dir[i][w]) st[i][v].erase({c[w][v] - c[w][i],w});
else st[v][i].insert({c[w][i] - c[w][v],w});
}
}
dir[u][w] ^= 1; dir[v][w] ^= 1;
v = u;
}
}
cout << ans + 1ll * n * INF << '\n';
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3596kb
input:
6 2 1 2 1 3 1 4 1 5 1 6 1 7 3 4
output:
12
result:
ok answer is '12'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
3 3 1 2 3 2 4 6 6 5 4 1 1 1
output:
8
result:
ok answer is '8'
Test #3:
score: -100
Time Limit Exceeded
input:
1000 10 734 303 991 681 755 155 300 483 702 442 237 256 299 675 671 757 112 853 759 233 979 340 288 377 718 199 935 666 576 842 537 363 592 349 494 961 864 727 84 813 340 78 600 492 118 421 478 925 552 617 517 589 716 7 928 638 258 297 706 787 266 746 913 978 436 859 701 951 137 44 815 336 471 720 2...