QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352314#7991. 最小环Kevin5307TL 4ms52068kbC++202.9kb2024-03-13 09:18:522024-03-13 09:18:53

Judging History

This is the latest submission verdict.

  • [2024-03-13 09:18:53]
  • Judged
  • Verdict: TL
  • Time: 4ms
  • Memory: 52068kb
  • [2024-03-13 09:18:52]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
set<int> G[400400];
ll f[400400],g[400400];
int u[400400],v[400400],tot;
map<int,int> E[400400];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	int n,m;
	cin>>n>>m;
	ll ans=0x3f3f3f3f3f3f3f3f;
	while(m--)
	{
		int u,v;
		ll w;
		cin>>u>>v>>w;
		if(u==v)
		{
			ans=min(ans,w);
			continue;
		}
		if(E[u].count(v))
		{
			int e=E[u][v];
			if(::u[e]==u)
				f[e]=min(f[e],w);
			else
				g[e]=min(g[e],w);
			G[u].insert(e);
			G[v].insert(e);
		}
		else
		{
			int e=++tot;
			f[e]=w;
			::u[e]=u;
			::v[e]=v;
			E[u][v]=E[v][u]=e;
			G[u].insert(e);
			G[v].insert(e);
		}
	}
	queue<int> q;
	for(int i=1;i<=n;i++)
		if(G[i].size()<=2)
			q.push(i);
	while(!q.empty())
	{
		int x=q.front();
		if(!G[x].size()) break;
		if(G[x].size()==1)
		{
			int e=*G[x].begin();
			int y=u[e]+v[e]-x;
			G[x].clear();
			G[y].erase(e);
			if(G[y].size()==2)
				q.push(y);
		}
		else
		{
			int e1=*G[x].begin();
			G[x].erase(e1);
			int e2=*G[x].begin();
			G[x].erase(e2);
			int y1=u[e1]+v[e1]-x;
			int y2=u[e2]+v[e2]-x;
			G[y2].erase(e2);
			if(u[e1]!=y1)
			{
				swap(u[e1],v[e1]);
				swap(f[e1],g[e1]);
			}
			if(u[e2]!=x)
			{
				swap(u[e2],v[e2]);
				swap(f[e2],g[e2]);
			}
			f[e1]+=f[e2];
			g[e2]+=g[e2];
			G[y2].insert(e1);
			v[e1]=y2;
		}
	}
	vector<int> vertex,edge;
	for(int i=1;i<=n;i++)
		if(G[i].size())
			vertex.push_back(i);
	for(auto x:vertex)
		for(auto e:G[x])
			if(x==u[e])
				edge.push_back(e);
	for(auto ban:edge)
	{
		static ll dist[300300];
		memset(dist,0x3f,sizeof(dist));
		priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
		dist[v[ban]]=0;
		pq.emplace(0,v[ban]);
		while(!pq.empty())
		{
			int x=pq.top().second;
			ll d=pq.top().first;
			pq.pop();
			if(dist[x]!=d)
				continue;
			for(auto e:G[x])
			{
				int y=u[e]+v[e]-x;
				ll nd=d+(u[e]==x?f[e]:g[e]);
				if(nd<dist[y])
				{
					dist[y]=nd;
					pq.emplace(nd,y);
				}
			}
		}
		ans=min(ans,f[ban]+dist[u[ban]]);
	}
	for(auto e:edge)
		swap(f[e],g[e]);
	for(auto ban:edge)
	{
		static ll dist[300300];
		memset(dist,0x3f,sizeof(dist));
		priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
		dist[v[ban]]=0;
		pq.emplace(0,v[ban]);
		while(!pq.empty())
		{
			int x=pq.top().second;
			ll d=pq.top().first;
			pq.pop();
			if(dist[x]!=d)
				continue;
			for(auto e:G[x])
			{
				int y=u[e]+v[e]-x;
				ll nd=d+(u[e]==x?f[e]:g[e]);
				if(nd<dist[y])
				{
					dist[y]=nd;
					pq.emplace(nd,y);
				}
			}
		}
		ans=min(ans,f[ban]+dist[u[ban]]);
	}
	if(ans==0x3f3f3f3f3f3f3f3f)
	{
		cout<<"-1\n";
		return 0;
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 52068kb

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: 0ms
memory: 47576kb

input:

1 0

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 4ms
memory: 47408kb

input:

1 1
1 1 1

output:

1

result:

ok single line: '1'

Test #4:

score: -100
Time Limit Exceeded

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:


result: