畅通工程续（最短路径）

浅浅的花香味﹌ 2022-08-01 15:55 172阅读 0赞

![Center][]

**这一题有点坑！就是如果两个点一样你得输出0，一直WA，最后发现了，我去！**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    const int infinity=0x3f3f3f3f;
    const int maxnum=2010;
    int map[maxnum][maxnum];//记录两个点的距离
    int vis[maxnum];//记录某一个点是否被访问！
    int dis[maxnum];//记录某一个点到第一个点的距离！
    int n,m;
    int djsta(int x,int y)
    {
        int i,j,mins,p;
        for(i=0;i<n;i++)
        {
            dis[i]=map[x][i];//记录某一个点到第一个点的距离！
        }
        memset(vis,0,sizeof(vis));//默认都未被访问！
        vis[x]=1;
        for(i=0;i<n;i++)
        {
            mins=infinity;
            for(j=0;j<n;j++)
            {
                if(!vis[j]&&dis[j]<mins)
                {
                    p=j;
                    mins=dis[j];
                }
            }
            vis[p]=1;
            for(j=0;j<n;j++)
            {
                if(!vis[j]&&dis[p]+map[p][j]<dis[j])
                {
                    dis[j]=dis[p]+map[p][j];
                }
            }
        }
        return dis[y];
    }
    int main()
    {
        int i,a,b,v,ans,j,s,e;
        while(cin>>n>>m)
        {
            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    map[i][j]=infinity;//设置最大值
                }
            }
            for(i=0;i<m;i++)
            {
                cin>>a>>b>>v;
                if(map[a][b]>v)
                {
                    map[a][b]=map[b][a]=v;//标记路径！
                }
            }
            cin>>s>>e;
            if(s==e)
            {
                cout<<0<<endl;
                continue;
            }
            ans=djsta(s,e);
            if(ans==infinity)
            {
                cout<<-1<<endl;
            }
            else
            {
                cout<<ans<<endl;
            }
        }
    }

[Center]: /images/20220731/7529283465ea494e9be8ae51d845aa2b.png