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();
}
            
       
    

Download