QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305714 | #7991. 最小环 | C1942huangjiaxu | WA | 175ms | 65640kb | C++14 | 1.8kb | 2024-01-15 21:06:41 | 2024-01-15 21:06:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=3005;
typedef long long ll;
const ll inf=1e18;
int n,m,id[N],ct;
bool dl[N],vis[M];
set<pair<int,ll> >oe[N],ie[N];
vector<pair<int,ll> >e[M],g[M];
queue<int>dq;
priority_queue<pair<ll,int> >q;
ll ans=inf,dis[M];
void check(int x){
if(dl[x])return;
if(oe[x].empty()||ie[x].empty()||oe[x].size()+ie[x].size()<3){
dq.push(x);
dl[x]=true;
}
}
void dijk(int S){
for(int i=1;i<=ct;++i)dis[i]=inf,vis[i]=false;
dis[S]=0;
q.push({0,S});
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=true;
for(auto [x,y]:e[u])if(dis[x]>dis[u]+y){
dis[x]=dis[u]+y;
q.push({-dis[x],x});
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y,z;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
if(x==y){
ans=min(ans,(ll)z);
continue;
}
oe[x].insert({y,z}),ie[y].insert({x,z});
}
for(int i=1;i<=n;++i)check(i);
while(!dq.empty()){
int u=dq.front();
dq.pop();
if(!oe[u].empty()&&!ie[u].empty()){
auto [x1,y1]=*oe[u].begin();
auto [x2,y2]=*ie[u].begin();
ie[x1].erase({u,y1});
oe[x2].erase({u,y2});
if(x1==x2)ans=min(y1,y2);
else ie[x1].insert({x2,y1+y2}),oe[x2].insert({x1,y1+y2});
check(x1),check(x2);
}else{
for(auto [x,y]:ie[u]){
oe[x].erase({u,y});
check(x);
}
for(auto [x,y]:oe[u]){
ie[x].erase({u,y});
check(x);
}
}
}
for(int i=1;i<=n;++i)if(!dl[i])id[i]=++ct;
for(int i=1;i<=n;++i)if(!dl[i]){
for(auto [x,y]:oe[i])e[id[i]].push_back({id[x],y});
for(auto [x,y]:ie[i])g[id[i]].push_back({id[x],y});
}
for(int i=1;i<=ct;++i){
dijk(i);
for(auto [x,y]:g[i])ans=min(ans,y+dis[x]);
}
if(ans==inf)puts("-1");
else printf("%lld\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 33124kb
input:
4 6 1 2 1 4 3 3 4 1 9 2 4 1 3 1 2 3 2 6
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 3ms
memory: 32164kb
input:
1 0
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 4ms
memory: 33312kb
input:
1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 132ms
memory: 65640kb
input:
258420 258419 33061 33062 767169384 212916 212917 1741339 229881 229882 896760805 173467 173468 273055172 233189 233190 800433307 10157 10158 126766550 174605 174606 552176083 224030 224031 886617880 229102 229103 783848581 67588 67589 510826095 233648 233649 879695751 214453 214454 867104578 153140...
output:
-1
result:
ok single line: '-1'
Test #5:
score: -100
Wrong Answer
time: 175ms
memory: 64548kb
input:
248016 248896 82688 82755 592665252 202847 203260 294408121 26821 28237 269132335 150967 152178 3125829 246069 247390 29492546 7470 7673 55843492 33975 35414 442802995 28451 28948 193736988 34484 34637 84441058 60168 60309 501991354 79579 79844 26854803 239672 239706 111702667 73548 73658 149840530 ...
output:
240890700
result:
wrong answer 1st lines differ - expected: '98674714245', found: '240890700'