校赛完了，这次校赛，做的很差，一个算法题没有，2个水题，1个贪心，概率DP，DP，数论题。DP还没开始研究，数论根本不会，数学太差了，省赛时卡数论，校赛依然卡数论，我擦，还是得继续学习啊！
一把锈迹斑斑的剑，只有不断的磨砺，才能展露锋芒！
以下为最短路总结：
最短路问题可分为：
二、每对顶点间的最短路径算法：Floyd；
(1).Dijkstra算法：
（经典的算法，可以说是最短路问题的首选事例算法，但是不能处理带负权的边，因为该算法要遍历的点过多，效率低下，用时长，仅限于小数据，不常用）
基本思想：
Dijkstra算法，本质上是利用贪心思想来不停的来进行贪心选择，查找最优解，开辟一个s[]，用来存放这些点，
dis[]用来存放所能经过的每个点的最短距离，并进行dis[]的更新操作。
模版如下：
int m,n,map[max][max],dis[max],s[max];
//int prev[max];//当前点的上一个节点
void Dijkstra(int v0)
{
for(int i = 0;i
(2).Bellman-Ford
(用来判断是否有回环，可处理带负权边 时间复杂度O(V*E).)
基本思想：（DP思想，查找最优解，并不断的进行松弛操作，但是算法浪费了许多时间做冗杂的松弛操作，效率降低）
void add()
{
scanf("%d%d%d",&u,&v,&w);
edge[l].u = u; edge[l].v = v; edge[l++].w = w;
edge[l].u = v; edge[l].v = u; edge[l++].w = w;
}
int Bellman(int cnt)
{
int i,j,flag;
for(i = 1;i <= N - 1;i++)
{
flag = 0;
for(j = 0;j <= count - 1;j++)
{
if(dis[edge[j].u]> dis[edge[j].v] + edge[j].w)
{ //松弛计算
dis[edge[j].u] = dis[edge[j].v] + edge[j].w;//更新dis[]数组，使其存储 源点->当前点的最短距离
flag = 1;
}
}
if(flag==0)//如果查找完,或者有些点达不到，跳出
break;
}
for(i = 0;i < count;i++)//判断是否有负环路
{
if(dis[edge[i].u] > dis[edge[i].v] + edge[i].w)//更新完dis[]后，如果还存在 该成立条件，则存在负环路
return 1;
} // 如1->2 权值2
return 0; // 2->3 权值5
// 3->1 权值-8
// 1->2->3->1 一次循环为-1 二次-2 三次....
}
（2）FLOYD
这个实在没什么好说的，做题目时，只要确定的 时间不超，就可以用，前提是记下，时间复杂度O(n*n*n).
void init()
{
for(i=0;i
map[i][k] + map[k][j] )
{
map[i][j]=map[i][k]+map[k][j];
}
}
}
}
}
(4)SPFA
书上说是在bellman-ford的基础上，添加一个队列操作，减少了其不必要的松弛操作。
我个人认为是在BFS搜索的基础上加了一步所谓的松弛操作，至于为什么叫松弛，不懂。
但是SPFA优化的很棒，以后最短路问题，尽量用它
void SPFA(int s，int e) S点 到e点
{
int l,r,i;
l=r=0;
memset(vt,0,sizeof(vt));
for(i=0;i
dis[p] + map[p][i])
{
dis[i] = dis[p] + map[p][i];
if(!vt[i])
{
q[r++] = i;
vt[i] = 1;
}
}
}
vt[p] = 0;
}
if(dis[e]!= inf)
printf("%d\n",dis[e]);
else
printf("-1\n");
}