Shortest Path

struct ShortestPath
{
    typedef int type;
    static const int inf=1e9;
    static const int __=100005;

    struct edge
    {
        int nex;type dis;
        edge() {}
        edge(int x,type y):
            nex(x),dis(y) {}
        bool operator<(const edge& b)const
        {
            return dis>b.dis;
        }
    };

    int n;
    type dis[__];
    bool vis[__];
    vector<edge>G[__];
    priority_queue<edge>Q;

    type& operator[](int x){return dis[x];}

    void init(int _n)
    {
        n=_n;
        for(int i=1;i<=n;++i)
        {
            vis[i]=false;
            dis[i]=inf;
        }
    }

    void add_edge(int x,int y,type dis)
    {
        G[x].push_back(edge(y,dis));
    }

    //先调用init
    void Dijkstra(int st)
    {
        dis[st]=0,Q.push(edge(st,0));
        while(!Q.empty())
        {
            int t=Q.top().nex;Q.pop();
            if(vis[t])continue;
            vis[t]=true;
            for(edge &x:G[t])
                if(!vis[x.nex] && dis[t]+x.dis<dis[x.nex])
                {
                    dis[x.nex]=dis[t]+x.dis;
                    Q.push(edge(x.nex,dis[x.nex]));
                }
        }
    }
    void clear()
    {
        for(int i=1;i<=n;++i)
            G[i].clear();
    }
}D;
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 什么问题是最短路问题 对路径的合理选取使得这条路径上的权重最后的结果符合题目要求的问题,一般都能够通过最短路算法解...
    kisslight阅读 5,496评论 1 1
  • [编程题]比较重量小明陪小红去看钻石,他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们...
    骇客与画家阅读 4,318评论 0 0
  • 本文将介绍三种常见的最短路算法:Dijkstra,Floyd,SPFA Dijkstra Dijkstra是有向图...
    maxkibble阅读 5,441评论 0 0
  • 与最小生成树有些不一样.在这里提出三种算法.dijkstra算法,是最普通也是最简单的.与prim算法有些类似,但...
    Anxdada阅读 3,369评论 0 0
  • 昨天在KTV参加了一个陌生朋友的生日聚会。灯光摇曳,年轻男男女女在喝酒唱歌,我这个吖叔坐在其中毫无违和感。虽然没有...
    三个耳阅读 1,001评论 0 0