hdu1874 最短路模板题

之所以做了第二道模板题还要写是因为发现了一些自己的问题

用的是dij 最简单的松弛

需要注意的地方是松弛的时候 判断dis[i]<dis[w]+tance[w][i]时 还要再判断 vis[i] 要保证这个点没有成为过最小点 即这个点不会是已经被松弛过的点

输入的时候要注意 可能会有重边的输入 每次输入的时候进行一次判断 如果输入的是较大值 就不用更换了

关于memset的使用 它只能用来设置0与-1 别的值会出现莫名的错误

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int dis[205];

int tance[205][205];

int vis[205];

int n,m;

int s,t;

void sc()

{

    vis[s]=1;

    for(int k=1;k<n;k++)

    {

        int minn=99999999;

        int w=s;

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

        {

            if(dis[i]<minn&&vis[i]==0)

            {

                w=i;

                minn=dis[i];

            }

        }

            vis[w]=1;

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

            {

                if(dis[i]>dis[w]+tance[w][i]&&vis[i]==0)

                {

                    dis[i]=dis[w]+tance[w][i];

                }

            }

    }

    return ;

}

int main(){

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

{

    int inf=99999999;

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

    for(int i=0;i<202;i++)

        for(int k=0;k<202;k++)

    {

        tance[i][k]=inf;

    }

    int a,b,c;

    for(int i=0;i<m;i++)

    {

        scanf("%d%d%d",&a,&b,&c);

        {

            if(tance[a+1][b+1]>c)

            {

                tance[a+1][b+1]=c;

                tance[b+1][a+1]=c;

            }

        }

    }

    scanf("%d%d",&s,&t);

    s+=1;

    t+=1;

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

    {

        tance[i][i]=0;

        dis[i]=tance[s][i];

    }

    dis[s]=0;

    sc();

    if(dis[t]==99999999)

        printf("-1\n");

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

}

}