为啥会有三个样例过不去?显示超时,大佬求看
查看原帖
为啥会有三个样例过不去?显示超时,大佬求看
675086
zdl__楼主2022/5/13 20:18

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n,m;
int dist[N],g[N][N];
bool st[N];
int prime()
{
	memset(dist,0x3f,sizeof dist);
	int res=0;
	for(int i=0;i<n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		 if(!st[j]&&(t==-1||dist[t]>dist[j]))
		     t=j;
		if(i&&dist[t]==0x3f3f3f3f)
			return 0x3f3f3f3f;
		if(i)
			res+=dist[t];
		st[t]=true;
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],g[t][j]);
		
	}
	return res;
}
int main()
{
	cin >> n >> m;
	int u, v, w;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(i ==j) 
				g[i][j] = 0;
	else 
		g[i][j] = 0x3f3f3f3f;
	
	while(m--)
	{
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = min(g[u][v], w);
	}
	int t = prime();
	if(t == 0x3f3f3f3f) 
		puts("orz");
	else 
		cout << t << endl;
}
2022/5/13 20:18
加载中...