NKCITY - Xây dựng thành phố
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#define maxn 1001
#define oo 100000000
int n,m,a[maxn][maxn],d[maxn],flag[maxn],x,y,z;
int min(int a,int b)
{
if(a<b) return a;
else return b;
}
int main()
{
//freopen("NKCITY.in","r",stdin);
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++)
{
d[i] = oo;
flag[i] = 0;
for(int j = 1;j<=n;j++)
a[i][j] = oo;
}
for(int i = 1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
a[x][y] = z;
a[y][x] = z;
}
for(int i = 1;i<=n;i++)
d[i]= a[1][i];
int KQ = 0,u=1;flag[1] = 1;d[1]=0;
while(true)
{
//printf("1");
int fl = 0, minn = oo;
for(int i = 1;i<=n;i++)
{
if(flag[i]==0 && d[i]<minn)
{
fl = i;
minn = d[i];
}
}
if(fl==0)
break;
else
{
u = fl;
flag[u] = 1;
if(d[fl]>KQ)
KQ = d[fl];
for(int i = 1;i<=n;i++)
d[i] = min(d[i],a[fl][i]);
}
}
printf("%d",KQ);
// getch();
}