题解 P1821 【[USACO07FEB]银牛派对Silver Cow Party】

· · 题解

看遍了所有题解，大家都没有写结构体版堆优化dijkstra的，而恰恰这个算法跑最短路是最实用的(那些线段树优化dijkstra的dalao先别说话。。。(noip也用不到))。spfa复杂度不稳定，可以被出题人轻松卡掉，所以，我来给各位发一遍堆优化dijkstra的题解，具体实现和思路看代码吧。

如果想练习做堆优化模板题联系一下的话：请 luogu P4779

下面献上我香喷喷的代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 1000+1
#define maxn1 100000+1
using namespace std;
inline ll qread()             //快读(不会的同学也可以用scanf,不推荐用cin,太慢了。。。)
{
    char c=getchar();ll num=0,f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) num=num*10+c-'0';
    return num*f;
}
ll n,m,dis[maxn],head[maxn],ans,num,zdl[maxn],t,s,maxx=-1;                 //dis表示起点到某个点的最短路，zdl为最后统计的最终每个点的最短路，maxx用来更新最大值。
struct Edge
{
    ll v,w,nxt;
}edge[maxn1];
inline void ct(ll u,ll v,ll w)   //链式前向星存图。
{
    edge[++num].v=v;
    edge[num].w=w;
    edge[num].nxt=head[u];
    head[u]=num;
}
struct node
{
    ll x,y;
    bool operator < (const node &a) const   //把大根堆重载成小根堆。
    {
        return y>a.y;
    }
};
inline void dijkstra()        //从某个点到终点。
{
    memset(dis,0x3f,sizeof(dis));  //初始化最短路数组为极大值。
    dis[s]=0;
    priority_queue<node>q;
    q.push((node){s,0});            //加入起点。
    while(!q.empty())
    {
        ll u=q.top().x,d=q.top().y;
        q.pop();
        if(d!=dis[u]) continue;
        for(ll i=head[u];i;i=edge[i].nxt)
        {
            ll v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w)  //dijkstra基本操作。
            {
                dis[v]=dis[u]+edge[i].w;
                q.push((node){v,dis[v]});
            }
        }
    }
}
inline void dijkstra2()     //从终点到某个点。
{
    memset(dis,0x3f,sizeof(dis));
    dis[t]=0;                     //加入终点。
    priority_queue<node>q;
    q.push((node){t,0});
    while(!q.empty())
    {
        ll u=q.top().x,d=q.top().y;
        q.pop();
        if(d!=dis[u]) continue;
        for(ll i=head[u];i;i=edge[i].nxt)
        {
            ll v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w)     //套路同上。
            {
                dis[v]=dis[u]+edge[i].w;
                q.push((node){v,dis[v]});
            }
        }
    }
}
int main()
{
    n=qread(),m=qread(),t=qread();
    for(int i=1,u,v,w;i<=m;++i)
    {
        u=qread(),v=qread(),w=qread();
        ct(u,v,w);           
    }
    for(int i=1;i<=n;++i)
    {
        s=i;
        dijkstra();
        zdl[i]=dis[t];           //更新每个点的当前最短路。
    }
    dijkstra2();
    for(int i=1;i<=n;++i)
    {
        zdl[i]+=dis[i];        //还要从终点跑回家。
        maxx=max(maxx,zdl[i]);  //更新最大值。
    }
    cout<<maxx<<'\n';
    return 0;                 //输出，完美落幕！
}

大家有什么不懂的地方可以在我的博客留言或私信问我哦！