minimum spanning tree

Plain version prim Algorithm

key word ： A dense picture , Time complexity O（n^2)
Each time, select a point that is not at the minimum distance of the connected block , Then update the data

Title Description

Given a n A little bit m Striped Undirected graph , There may be Double edge and self ring , The edge weight may be negative .

Find the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.

Given an undirected graph with weights G=(V, E), among V Represents the set of points in the graph ,E Represents a set of edges in a graph ,n=|V|,m=|E|.

from V All of n A vertex and E in n-1 An undirected connected subgraph composed of edges is called G A spanning tree of , The spanning tree in which the sum of the weights of the edges is the smallest is called an undirected graph G The minimum spanning tree of .

Input format

The first line contains two integers n and m.

Next m That's ok , Each line contains three integers u,v,w, Indication point u Sum point v There is a weight of w The edge of .

Output format

All in one line , If there is a minimum spanning tree , Then an integer is output , Represents the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.

Data range

1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
The absolute values of the edge weights of the edges involved in the graph do not exceed 10000.

sample input ：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
sample output ：

6

Code

#include<bits/stdc++.h>
using namespace std;
// A dense picture  
const int N=510,M=10010,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int d[N];
bool v[N];

int prim(){
    
	memset(d,0x3f,sizeof d);
	
	int res=0;
	for(int i=0;i<n;i++){
    
		int t=-1;
		
		for(int j=1;j<=n;j++)
		  if(!v[j]&&(t==-1||d[t]<d[j]))
		    t=j;
		
		if(i&&d[t]==INF) return -1;// Cannot generate minimum spanning tree 
		v[t]=true;
		if(i) res+=d[t];
		
		for(int j=1;j<=n;j++)
		  d[j]=min(d[j],g[t][j]);// Update distance from point to set  
		
	}
	return res;
}

int main(){
    
    cin>>n>>m;
	
	memset(g,0x3f,sizeof g);
	while(m--){
    
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=g[v][u]=min(g[u][v],w);
	} 
	int t=prim();
	if(t==-1) cout<<"impossible"<<endl;
	else cout<<t<<endl;
	
	return 0;
}