感觉自己太懒了，以后每天更博客激励自己吧。 //时间复杂度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});
}
}
}
}
}