http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=400#problem/A
这道题不仅用到了Dijkstra,还要求最小生成树

#include<stdio.h>
#include<string.h>
int map[300][105],weight[105],flag[105],infinite=2147483647;//无穷大存为pow(2,31)
int main(){
    int n,m,i,j,x,y,z,min;
    while(scanf("%d%d",&n,&m),n){
        for(i=1;i<=m;i++)//给此图每个元素赋上最大值
            for(j=1;j<=m;j++)
                map[i][j]=infinite;
        for(i=0;i<n;i++){
            scanf("%d%d%d",&x,&y,&z);
            if(map[x][y]>z)
            map[x][y]=map[y][x]=z;//给数组赋上输入的权值
        }
        for(i=1;i<=m;i++)
            weight[i]=map[1][i];//a数组存矩阵一行的值
        memset(flag,0,sizeof(flag));
        x=0;
        flag[1]=1;//输入的顶点数至少为二
        for(i=1;i<m;i++){
            min=infinite;//赋初值无穷大,即两点不连通
            for(j=1;j<=m;j++)
                if(flag[j]==0&&min>weight[j]){//min>weight[j]用于找出与1~n-1的点相邻且权值最小的点
                    min=weight[j];
                    z=j;//通过z向矩阵下层转移
                }
            flag[z]=1;//标记已经访问过的顶点
            if(min==infinite){//若出现多个连通分支则不能实现
                printf("?\n");
                break;
            }
            x+=min;//加和每次得到的最小权值
            for(j=1;j<=m;j++)//用a数组更新矩阵下一行的值,即访问与最小权值点相邻的点
                if(flag[j]==0&&weight[j]>map[z][j])
                    weight[j]=map[z][j];
        }
        if(x>=m)//成本为正整数则两点权值至少为1
            printf("%d\n",x);
    }
    return 0;
}
 

发表评论

电子邮件地址不会被公开。

Post Navigation