dijkstra算法的应用（poj2387）+堆优化【还没学C艹很尴尬，不理解的先不写了，未完，待续...】

一题非常简单的最短路题目，但是我就是很撒比的错在了，1.初始化；2.判断重边

堆优化，使用优先队列的堆优化；复杂度：O(ElogE);

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#include <queue>

#include <set>

#include <stack>

#include <algorithm>

using namespace std;

#define PI acos(-1.0)

#define INF 0x3f3f3f3f

#define INH 0x3f3f3f3f

#define N 1010

int dis[N];

int a[N][N];

int vis[N];

int n;

void init()//初始化i->i为0，i->j为INF

{

    int i,j;

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

        {

            if(i==j)

                a[i][j]=0;

            else

                a[i][j]=INF;

        }

    }

}

void dijs()

{

    int i,j;

    memset(vis,0,sizeof(vis));

    int k;

    for(i=1;i<=n;i++)

    {

        dis[i]=a[1][i];

    }

    vis[1]=1;

    dis[1]=0;

    for(i=1;i<=n-1;i++)

    {

        int mimi=INF;

        k=0;

        for(j=1;j<=n;j++)

        {

            if(mimi>dis[j]&&!vis[j])

            {

                mimi=dis[j];

                k=j;

            }

        }

        vis[k]=1;

        for(j=1;j<=n;j++)

        {

            if(dis[j]>(dis[k]+a[k][j])&&!vis[j]&&a[k][j]!=INF)

            {

                dis[j]=dis[k]+a[k][j];

            }

        }

    }

}

int main()

{

    int j,i,t;

    while(~scanf("%d%d",&t,&n))

    {

        int u,v,w;

        init();

        for(i=0;i<t;i++)

        {

            scanf("%d%d%d",&u,&v,&w);

            if(a[u][v]>w)    //判断重边

            a[u][v]=a[v][u]=w;

        }

        dijs();

        printf("%d\n",dis[n]);

    }

    return 0;

}