感觉自己太懒了，以后每天更博客激励自己吧。

//时间复杂度O（n*n）的最短路算法

//首先需要设置一个访问数组v[maxn]，一个数组d[maxn]，

memset(v,,sizeof(v));

for(int i=;i<n;i++) d[i]=(i==?:inf);

for(int i=;i<n;i++)

{

    for(int y=;y<n;y++)

    {

    int x,m=inf;

    if(!v[y]&&d[y]<=m) m=d[x=y];

    v[x]=;

    for(int y=;y<n;y++)

    if(d[y]>d[x]+w[x][y])

      {

        d[y]=d[x]+w[x][y];

        fa[y]=x;  //fa数组记录y节点的父节点，如果题目要求输出最短路路径，则顺着fa数组输出就可以了

      }

      //不要求输出最短路径时的另一种写法

      //d[y]=min(d[y],d[x]+w[x][y]);只需要更新d[i]就可以了

    }

}

//时间复杂度为O（m*logn的算法）

//利用vector数组实现图的存储

//edges数组存储每条边的信息，G[i]存储从i号节点出发，

//思想，在原先O（n*n）算法当中，每次查找最小的d[i]点，都要for循环一遍花去大量的执行步骤

//所以现在用一个优先队列来保存每个节点到源点的距离d[i]，每次都弹出最小的d[i]省去查找的时间

//此外借助广搜的思想，源节点先入队，然后它的每个子节点如果满足条件在队，每个节点都会最多被便利一次

//这对应了第一种朴素算法中的最外层for循环把每个节点都 遍历一遍

struct Edge{

    int from,to,dist;

    Edge(int u,int v,int d):from(u),to(v),dist(d) {};

};

struct Dijkstra()

{

    int n,m;

    vector<Edge> edges;

    vector<int> G;

    bool down[maxn];

    int d[maxn];

    int p[maxn];

    void init()

    {

        for(int i=;i<n;i++)

        G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,int dist)

    {

        edges.push_back();//将边加入边集

        m=edges.size;

        G[from].push_back(m-);//由于下标是从零开始的，所以当加入以from开头的边时，这条边的编号为edges的大小-1 

    }

    struct heapnode{

        int d,u;  //定义了每个节点的优先级比较方法，按照其离源点的距离，小的先输出

        bool oprator <(const heapnode& rhs) const {

        return d>rhs.d;

        }

    };

    void dijkstra(int s)

    {

           priority_queue<heapnode> Q;

        for(int i=;i<n;i++) //初始化每个点到源点的距离为无穷

        d[i]=inf;

        d[]=;  //源点到自身的距离初始化为0；

        memset(done,,sizeof(done));

        Q.push((heapnode){,s});

        while(!Q.empty())

        {

        heapnode x=Q.top();

                 Q.pop();

            for(int i=;i<G[x.u].size;i++)

            {

            Edge& e=edges[G[x.u][i]];//G[i]数组保存的时i结点的各个边在e数组中对应的边号

                  if(d[e.to]>d[e.from]+e.dist)//如果到e.to有更短的路，则更新d数组

                  {

                      d[e.to]=d[e.from]+e.dist;

                      p[e.to]=G[x.u][i];//保存到当前节点e.to的最短路径的上一条边是谁

                      Q.push((heapnode){d[e.to],e.to});

                  }

            }

        }

    }

 }