C--最短路

以你之姓@ 2022-07-12 08:26 138阅读 0赞

#### Problem Description ####

给出一个带权无向图，包含n个点，m条边。求出s，e的最短路。保证最短路存在。

#### Input ####

多组输入。

对于每组数据。

第一行输入n，m(1<= n && n<=5\*10^5,1 <= m && m <= 2\*10^6)。  
接下来m行，每行三个整数，u,v,w,表示u，v之间有一条权值为w(w >= 0)的边。  
最后输入s，e。

#### Output ####

对于每组数据输出一个整数代表答案。

#### Example Input ####

3 1
    1 2 3
    1 2

#### Example Output ####

SPFA算法：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define maxn 500005
    #define max 0x3f3f3f3f
    struct node
    {
        int v;
        int w;
        int next;
    }map[4000005];
    int queue[maxn];
    int dist[maxn];
    int book[maxn];
    int head[maxn];
    int front,rear,n,cnt;
    
    void add(int u,int v,int w)
    {
        map[cnt].v=v;
        map[cnt].w=w;
        map[cnt].next=head[u];
        head[u]=cnt++;
    }
    
    void spfa(int s)
    {
        int i,u,v,w;
        for(i=0;i<=n;i++)
        {
            book[i]=0;
            dist[i]=max;
        }
        dist[s]=0;
        book[s]=1;
        rear=(rear+1)%maxn;
        queue[rear]=s;
        while(front!=rear)
        {
            front=(front+1)%maxn;
            u=queue[front];
            book[u]=0;
            for(i=head[u];i!=-1;i=map[i].next)
            {
                v=map[i].v;
                w=map[i].w;
                if(dist[v]>dist[u]+w)
                {
                    dist[v]=dist[u]+w;
                    if(!book[v])
                    {
                        rear=(rear+1)%maxn;
                        queue[rear]=v;
                        book[v]=1;
                    }
                }
            }
        }
    }
    int main()
    {
        int i,m,u,v,w,s,e;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            front=rear=cnt=0;
            memset(head,-1,sizeof(head));
            while(m--)
            {
                scanf("%d%d%d",&u,&v,&w);
                add(u,v,w);
                add(v,u,w);
            }
            scanf("%d%d",&s,&e);
            spfa(s);
            printf("%d\n",dist[e]);
        }
        return 0;
    }