POJ 2387 Til the Cows Come Home

POJ 2387 Til the Cows Come Home

#include <iostream>
#include<string.h>


using namespace std;
const int MAXN=2010;
const int INF=99999999;

bool vis[MAXN];
int pre[MAXN];
int cost[MAXN][MAXN];
int lowcost[MAXN];
int beg;
int n,t;
void Dijkstra(int cost[][MAXN],int lowcost[],int beg)
{
    for(int i=0; i<n; i++)
    {
        lowcost[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=0; j<n; j++)
    {
        int k=-1;
        int _min=INF;
        for(int i=0; i<n; i++)
        {
            if(!vis[i]&&lowcost[i]<_min)
            {
                _min=lowcost[i];
                k=i;
            }
        }
        if(k==-1)
        {
            break;
        }
        vis[k]=true;
        for(int i=0; i<n; i++)
        {
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
            {
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
        }
    }
}


int main()
{

    while(cin>>t>>n)
    {
        memset(vis,0,sizeof(vis));
        memset(pre,0,sizeof(pre));
        memset(cost,0,sizeof(cost));
        memset(lowcost,0,sizeof(lowcost));
        int from,to,c;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==j)
                    cost[i][j]=0;
                else
                    cost[i][j]=cost[j][i]=INF;
            }
        }
        for(int i=0; i<t; i++)
        {
            cin>>from>>to>>c;
            if(cost[from-1][to-1]>c)
            {
                cost[from-1][to-1]=c;
                cost[to-1][from-1]=c;
            }

        }

        beg=n-1;
        Dijkstra(cost,lowcost,n-1);
//        for(int i=0;i<n;i++)
//        cout<<lowcost[i]<<" ";
//        cout<<endl;
//        for(int i=0;i<n;i++)
//            cout<<pre[i]<<" ";
//        cout<<endl;
        cout<<lowcost[0]<<endl;
    }

    return 0;
}