QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305714#7991. 最小环C1942huangjiaxuWA 175ms65640kbC++141.8kb2024-01-15 21:06:412024-01-15 21:06:41

Judging History

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

  • [2024-01-15 21:06:41]
  • 评测
  • 测评结果:WA
  • 用时:175ms
  • 内存:65640kb
  • [2024-01-15 21:06:41]
  • 提交

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'