一道算法题，不知错哪
题目见http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1056

我用的是prim算法，参考http://www.cnblogs.com/bofengqiye/archive/2012/05/05/2484542.html

程序如下：

C/C++ code

#include <stdio.h>#define MAX 0x7fffffffint graph[110][110];void Initial(int schoolNum,int tunnelNum);void Prim(int schoolNum,int tunnelNum);int main(){    int schoolNum,tunnelNum;    scanf("%d%d",&schoolNum,&tunnelNum);    Initial(schoolNum,tunnelNum);    Prim(schoolNum,tunnelNum);    return 0;}void Initial(int schoolNum,int tunnelNum){    int src_schoolNo,des_schoolNo,interLength;    int i,j;    for (i=1;i<=schoolNum;i++)    {        for (j=1;j<=schoolNum;j++)        {            graph[i][j]=MAX;        }    }    for (i=1;i<=tunnelNum;i++)    {        scanf("%d%d%d",&src_schoolNo,&des_schoolNo,&interLength);        graph[src_schoolNo][des_schoolNo]=interLength;    }}void Prim(int schoolNum,int tunnelNum){    //TotalLength地道的总长度，TotalCost总花费，schoolConnNum地道能连接的学校数    int TotalLength=0,TotalCost,Min,minIndex,schoolConnNum=1;     //lowLength[i]不属于MST中的顶点i到MST中顶点的最小距离，isUsed表明学校是否属于地道，即是否在MST中    int lowLength[110],isUsed[110];     int i,j,cost[3];  //cost数组是三种币的个数    char *Unit[3]={"ac","ds","al"}; //Unit数组为三种币的单位    for (i=1;i<=schoolNum;i++) //地道起点为1号学校    {        lowLength[i]=graph[1][i];        isUsed[i]=0;    }    isUsed[1]=1;  //1号学校在MST中    for (i=1;i<schoolNum;i++)    {        Min=MAX;        minIndex=-1;        //找最短距离        for (j=1;j<=schoolNum;j++)        {            if (isUsed[j]==0&&lowLength[j]<Min)            {                minIndex=j;                Min=lowLength[j];            }        }        //找到        if (minIndex!=-1)        {            schoolConnNum++;            TotalLength+=Min;            isUsed[minIndex]=1;            for (j=1;j<=schoolNum;j++)  //更新数组            {                if (graph[minIndex][j]<lowLength[j])                {                    lowLength[j]=graph[minIndex][j];                }            }        }    }    if (schoolConnNum!=schoolNum) //最小生成树的节点数不等于学校总数，地道长度为0    {        TotalLength=0;    }    TotalCost=TotalLength*7;    i=0; //币种下标    cost[0]=TotalCost%29;    TotalCost/=29;    if (TotalCost)    {        cost[1]=TotalCost%17;        TotalCost/=17;        i++;        if (TotalCost)        {            cost[2]=TotalCost;            i++;        }    }    //输出    for (j=i;j>=0;j--)    {        printf("%d%s",cost[j],Unit[j]);    }    printf("\n");}

不管如何修改，都是：Wrong Answer at Test 3

求高手

[解决办法]
这是无向图，所以需要
graph[src_schoolNo][des_schoolNo]=graph[des_schoolNo][src_schoolNo]=interLength;

有向图的mst叫最小树形图，比prim/kruskal什么的复杂多了。