Prim算法的时间复杂度分析

Prim算法是很经典的一个最小生成树算法，用优先队列实现时间复杂度为O(mlogm)。然后我在HDU做了道题目，提交后时间大概300ms。后来网上搜了个不是用优先队列实现的算法【附此代码如下】，时间只花了大概200ms，但是他的时间复杂度理论上不是应该是O(n*n)，应该更慢才是啊，请高手指点这是怎么回事？
代码：
#define MaxSize 105
#define INIT 999999999

int Graph[MaxSize][MaxSize];
long sum;
bool visited[MaxSize];

int NumOfVillage;

void Prim()
{
    int i,j;
    sum = 0;
    int dist[MaxSize];
    int min,locate;
    memset(visited,0,sizeof(visited));
    for(i=1;i<=NumOfVillage;i++)
        dist[i] = Graph[1][i];
    visited[1] = true;
    for (j=1;j<=NumOfVillage;j++)
    {
        min = INIT;
        for (i=1;i<=NumOfVillage;i++)
        {
            if(!visited[i]&&dist[i]<min)
            {
                min = dist[i];
                locate = i;
            }
        }   
        visited[locate] = true;
        for (i=1;i<=NumOfVillage;i++)
        {
            if (!visited[i]&&dist[i]>Graph[locate][i])
            {
                dist[i] = Graph[locate][i];
            }
        }

    }
    for (i=1;i<=NumOfVillage;i++)
    {
        sum+=dist[i];
    }
}