AcWing 858. java 把t=0更简单
原题链接
简单
作者:
季之秋
,
2021-01-21 16:48:41
,
所有人可见
,
阅读 340
import java.util.*;
public class Main{
static int n,m,N=510,INF=0x3f3f3f3f;
static int g[][]=new int[N][N];
static boolean st[]=new boolean[N];
static int d[]=new int[N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++) Arrays.fill(g[i],INF);
while(m--!=0){
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
g[a][b]=g[b][a]=Math.min(g[a][b],c);
}
int z=prim();
System.out.println(z==INF?"impossible":z);
}
static int prim(){
Arrays.fill(d,INF);
int ref=0;
for(int i=0;i<n;i++)
{
int t=0;
for(int j=1;j<=n;j++)
{
if(!st[j]&&d[t]>=d[j]) t=j;//如果写成> i=0的时候t=j就不会执行
}//那么g[0][j]就一直是INF或0,如果是0就一直是最小的,如果是INF就都是INF
//那么i=1的时候就会return INF,因为d数组里全部是INF
if(i!=0&&d[t]==INF) return INF;
if(i!=0) ref+=d[t];
for(int j=1;j<=n;j++)
{
d[j]=Math.min(d[j],g[t][j]);
}
st[t]=true;
}
return ref;
}
}