花了一些时间看了一下最短路，理论ac了这个专题，有些题目自己也写了一下。写几道有代表性的把。
C（这题题解不想自己写了就贴的网上的http://blog.csdn.net/HowardEmily/article/details/53449396?locationNum=1&fps=1）
题意：要从城市1到城市N运送货物，有M条道路，每条道路都有它的最大载重量，问从城市1到城市N运送最多的重量是多少。
其实题意很简单，就是找一条1-->N的路径，在不超过每条路径的最大载重量的情况下，使得运送的货物最多。一条路径上的最大
载重量为这个路径上权值最小的边;
思路:dijkstra 的变形,我们只需要每次选取离源点载货量最多的那条边,然后通过它去松弛所有路径上的最大载重量;
说一下为什么要每次选取离源点权值最大的那个点去松弛,我们知道原始的dijkstra是每次选取离源点最近的边去松弛使得求出的源
点到其余点的单源最短路径最短,那么我们这里希望让它路径上权值最小的边尽可能的大,我们就需要去选取离源点权值最大的点,使
得它的该路径的最大载重量大一些;
H
题意：输入：第一行输入两个数n，m，表示牛的数量和m场比赛。接下来m行表示m场比赛，每行两个数a，b，表示a打败了b，求有几头牛的排名是确定的。
思路：弗洛伊德，算出每头牛被多少头牛打败，胜过多少头牛，如果这两个数加起来等于n-1就可以确定排名。
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) v[k][j] |= v[k][i] & v[i][j];I
题意：给出一些种类的货币以及它们之间的转换关系，求是否有货币可以经过一段时间的转换之后便的比之前更多。
思路：spfa判断“负环”就是和判负环类似，如果入队超过n次说明可以无限增值。注意一下这题数据比较水，图都是联通的，以后要考虑一下图不联通的情况。
M题之前的文章里写过了
O
题意：给出一个有向图和一些边，可以求出边权，求单源最短路。如果<3 或者 达不到 输出问号 不然输出dis[v]。
思路：spfa，判断时，如果一个点在负环内，dfs将这个点能到达的所有点都做标记，即做标记的这些点都是达不到的（无法求出最短路）。
P
题意：输入第一行T表示有T组数据，每组数据第一行三个数n,m,c，分别表示点数，边数和相邻层节点之间的距离。下一行有n个数，表示第i个节点在第几层。接下来m行，每行三个数x，y，z，表示x到y的距离为z。求点1到点n的最短路。
这题就注意一下写的时候不用相邻层再连边了，直接在spfa里面，多两个循环就好啦。就是把每一层的节点都存在vector里面，一个点出队的时候，除了算和它邻接的节点，再算和它相邻层的节点就行了，很简单的。
Q
题意 : 给出一个图，求起点到终点最短路的条数。
思路: dijkstra预处理，把所有最短路的边加入新图后，最大流求最短路条数。
R
题意：
矩阵Xij，应满足条件：
1.X 12+X 13+...X 1n=1 2.X 1n+X 2n+...X n-1n=1 3.for each i (1<i<n), satisfies ∑X ki (1<=k<=n)=∑X ij (1<=j<=n).
题目中另给矩阵Cij，求使得∑C ij*X ij(1<=i,j<=n)最小的Xij。
这又是一个把矩阵和图互相转换的题。
题解看的kuangbin的博客，因为写的很清楚就直接复制了：
解题的关键在于如何看出这个模型的本质。 3个条件明显在刻画未知数之间的关系，从图论的角度思考问题，容易得到下面3个结论： 1.X12+X13+...X1n=1 于是1号节点的出度为1 2..X1n+X2n+...Xn-1n=1 于是n号节点的入度为1 3.∑Xki =∑Xij 于是2~n-1号节点的入度必须等于出度 于是3个条件等价于一条从1号节点到n号节点的路径，故Xij=1表示需要经过边(i,j)，代价为Cij。Xij=0表示不经过边(i,j)。注意到Cij非负且题目要求总代价最小，因此最优答案的路径一定可以对应一条简单路径。 最终，我们直接读入边权的邻接矩阵，跑一次1到n的最短路即可，记最短路为path。 以上情况设为A 情况B： 从1出发，走一个环（至少经过1个点，即不能是自环），回到1；从n出发，走一个环（同理），回到n。 容易验证，这是符合题目条件的。且A || B为该题要求的充要条件。 由于边权非负，于是两个环对应着两个简单环。 因此我们可以从1出发，找一个最小花费环，记代价为c1,再从n出发，找一个最小花费环，记代价为c2。（只需在最短路算法更新权值时多加一条记录即可：if(i==S) cir=min(cir,dis[u]+g[u][i])） 故最终答案为min(path,c1+c2)。
S
题意：有n只牛要按照由1到n的顺序排在一条直线上，多头牛可以在同一个点。其中有一些牛互相喜欢，另一些牛互相讨厌。题目中给出互相喜欢的牛，每行三个数，表示互相喜欢的牛的编号和它们相距最远的距离，互相讨厌的牛也是，每行三个数，表示牛的编号和相距最近的距离。现在求1号牛和n号牛最远的距离。
思路：很显然的差分约束系统，注意一下如果用spfa求完之后n号牛的d没有发生变化，说明这些不等式没有限制到它，可以无限远，而要是出现负环则说明无解。
