复习，图论经典，noip必备。
1.floyed
求任意两点之间最短路，dp的思想，O（n^3）。
void Floyed(){ memset(d,0x3f,sizeof(d)); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); }
2.dijkstra
求单源最短路的优秀算法，本质贪心，所以怕负边权。一般堆优化，比普通的好打，O（nlogn）。
struct node{ int id,val; friend bool operator < (const node &a,const node &b){ return a.val>b.val; } }now; struct Edge{ int ed,nex,w; }edge[]; void dijs(int st){ priority_queue<node>q; memset(dis,0x7f,sizeof(dis)); memset(v,0,sizeof(v)); dis[st]=0; now.id=st;now.val=0; q.push(now); while(!q.empty()){ now=q.top();q.pop(); int x=now.id; if(v[x]) continue; v[x]=1; for(int i=first[x];i;i=edge[i].nex){ int y=edge[i].ed; if(dis[y]>dis[x]+edge[i].w){ dis[y]=dis[x]+edge[i].w; now.id=y;now=dis[y]; q.push(now); } } }return ; }
3.spfa
求单源最短路的玄学算法，可以碾压dijkstra，也可以被素质出题人卡到自闭，不怕负边权，看起来和堆优的dijkstra神似，但是少一些内容，好打一些，也好理解，O（k*n）。k看入队次数，稀疏图约等于5，碰到稠密图很可能退化，特殊构造必死。
struct EDGE{ int ed,nex,w; }edge[]; void spfa(int st){ queue<int>q; memset(dis,0x7f,sizeof(dis)); memset(v,0,sizeof(v)); q.push(st); dis[st]=0; v[st]=1; while(!q.empty()){ int x=q.front(); for(int i=first[x];i;i=edge[i].nex){ int y=edge[i].ed; if(dis[y]>dis[x]+edge[i].w){ dis[y]=dis[x]+edge[i].w; if(!v[y]){ v[y]=1; q.push(y); } } } v[x]=0; q.pop(); }return; }
学最短路时还是个…现在看起来还好。
原文：https://www.cnblogs.com/Yu-shi/p/11142337.html
