C++ RQNOJ 星门龙跃

怼烎@ 2021-11-01 12:22 243阅读 0赞

[**最短路讲解**][Link 1]

**[RQNOJ 星门龙跃][RQNOJ]**

**邻接链表+优先队列.Dijkstra**

#include<cstdio>
    #include<cstring>
    #include<queue>
    #define inf 0x3f3f3f3f
    using namespace std;
    typedef pair<int,int> pii;
    priority_queue<pii,vector<pii>,greater<pii> >q;
    struct edge{
        int x,z,next;
    }e[300005];
    int n,m,f[30005],vis[30005],tot=1,head[30005];
    void adde(int u,int x,int z)//建树
    {
        e[tot].x=x;
        e[tot].z=z;
        e[tot].next=head[u];
        head[u]=tot++;
    }
    int main()
    {
        int a,b,c;
        memset(head,-1,sizeof(head));
        memset(f,inf,sizeof(f));    
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            adde(a,b,c);
            adde(b,a,c);
        } 
        f[1]=0;
        q.push(make_pair(f[1],1));
        while(!q.empty())
        {
            int u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(int k=head[u];k!=-1;k=e[k].next)
            {
                int t=e[k].x;
                if(f[u]+e[k].z<f[t]) 
                {
                    f[t]=f[u]+e[k].z;
                    q.push(make_pair(f[t],t));    
                }            
            }
        }
        printf("%d",f[n]);
        return 0;
    }

**SPFA**

#include<cstdio>
    #include<cstring>
    #include<queue>
    #define inf 0x3f3f3f3f
    #define maxm 30001
    using namespace std;
    queue<int> q;
    struct edge{
        int x,z,next;
    }e[150001];
    int n,m,f[maxm],vis[maxm],tot=1,head[maxm];
    void adde(int u,int x,int z)
    {
        e[tot].x=x;
        e[tot].z=z;
        e[tot].next=head[u];
        head[u]=tot++;
        e[tot].x=u;
        e[tot].z=z;
        e[tot].next=head[x];
        head[x]=tot++;    
    }
    int main()
    {
        int a,b,c,p;
        memset(head,-1,sizeof(head));
        memset(f,inf,sizeof(f));
        memset(vis,0,sizeof(vis));    
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            adde(a,b,c);
        } 
        f[1]=0;
        q.push(1);
        vis[1]=1;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int k=head[u];k!=-1;k=e[k].next)
            {
                p=e[k].x;
                if(f[p]>f[u]+e[k].z) 
                {
                    f[p]=f[u]+e[k].z;    
                    if(!vis[p])
                    {
                        q.push(p);
                        vis[p]=1;
                    }
                }
            }
        }
        printf("%d",f[n]);
        return 0;
    }

转载于:https://www.cnblogs.com/mzyczly/p/11209772.html

[Link 1]: https://www.cnblogs.com/mzyczly/p/11028962.html
[RQNOJ]: http://www.rqnoj.cn/problem/341