Dijkstra模板

struct edge
{
    int to,cost;
};
vector<edge>v[1010];
typedef pair<int,int>p;
int dis[1010];
int n;
void dijkstra()
{
    fill(dis+1,dis+n+1,INF);
    dis[1]=0;
    priority_queue<p,vector<p>,greater<p> >q;
    q.push(p(0,1));
    while(!q.empty())
    {
        p temp=q.top();
        q.pop();
        int w=temp.first;int id=temp.second;
        if(w>dis[id])continue;
        for(int i=0;i<v[id].size();i++)
        {
            edge &e=v[id][i];
            if(w+e.cost<dis[e.to])
            {
                dis[e.to]=w+e.cost;
                q.push(p(dis[e.to],e.to));
            }
        }
    }
}

floyd模板

for(k=1;k<=n;k++)    
for(i=1;i<=n;i++)    
for(j=1;j<=n;j++)    
dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);

spfa模板

struct edge
{
    int to;
    int cost;
};
vector<edge>v[2510];
double dis[2510];
bool vis[2510];
int cnt[2510];
int n,tp;
double w;
bool spfa()
{
    fill(dis+1,dis+1+n,INF);
    fill(vis+1,vis+1+n,false);
    fill(cnt+1,cnt+1+n,0);
    queue<int>q;q.push(1);
    vis[1]=true;dis[1]=0;cnt[1]++;
    while(!q.empty())
    {
        tp=q.front();vis[tp]=false;
        q.pop();
        for(int i=0;i<v[tp].size();i++)
        {
            edge &e=v[tp][i];
            if(dis[tp]+e.cost<dis[e.to])
            {
                dis[e.to]=dis[tp]+e.cost;
                if(!vis[e.to])
                {
                   q.push(e.to);
                   vis[e.to]=true;
                   cnt[e.to]++;
                   if(cnt[e.to]>n)return true;   //判断负环
                }
            }
        }
    }
    return false;
}

POJ 2253

题意：

​ 有两只青蛙和若干块石头，现在已知这些东西的坐标，两只青蛙A坐标和青蛙B坐标是第一个和第二个坐标，现在A青蛙想要到B青蛙那里去，并且A青蛙可以借助任意石头的跳跃，而从A到B有若干通路，问从A到B的所有通路上的最大边。

解题思路：

​ 求所有通路中间最长的一段路的最小值，让dis[i]存从1到i的最长的一段路，然后max(dis[id],e.cost)<dis[e.to]更新即可。

POJ 1797

题意：

​ 找一条从 1 到 n 的道路，使得这条道路的每段距离中的最小值最大。

解题思路：

​ 求所有通路中间最短的一段路的最大值，让dis[i]存从1到i的最短的一段路，然后min(dis[id],e.cost)>dis[e.to]更新即可。

POJ 3268

题意：

​ 有编号为1－N的牛，它们之间存在一些单向的路径。给定一头牛的编号，其他牛要去拜访它并且拜访完之后要返回自己原来的位置，求这些牛中所花的最长的来回时间是多少。

解题思路：

​ 返回的最短路直接把原来的出边变成入边再dijkstra一次即可。

POJ 3660

题意：

​ 有n头牛比赛，m种比赛结果，最后问你一共有多少头牛的排名被确定了，其中如果a战胜b，b战胜c，则也可以说a战胜c，即可以传递胜负。求能确定排名的牛的数目。

解题思路：

​ 传递闭包再根据出度+入度即可。

POJ 1860

题意：

​ 给定N种货币，某些货币之间可以相互兑换，现在给定一些兑换规则，问能否从某一种货币开始兑换，经过一些中间货币之后，最后兑换回这种货币，并且得到的钱比之前的多。

解题思路：

​ 判断有没有正权回路，如果有正权回路的话会一直循环下去，就相当于最短路里面判断有没有负权回路，dis[i]里面装可以换的钱，如果松弛成功（钱变多了）就更新，spfa计数判断某个点进入队列的次数超过n次就有正权回路。

POJ 3159

题意：

​ 给n个人分糖果，m组数据a，b，c；意思是a比b少的糖果个数绝对不超过c个，也就是d(b)-d(a) < c，求1比n少的糖果数的最大值。

解题思路：

​ 差分约束，因为要使dis[B]<dis[A]+e.cost，所以修改一下松弛条件dis[id]+e.cost<dis[e.to]即可（因为刚开始初始化的dis[e.to]是INF，所以松弛要使它变小）。

给出一些形如x-y<=b不等式的约束，问你是否满足有解的问题，这类问题可以转换成图论里的最短路径问题。

在单源最短路径的算法中有一步是“若d[v] > d[u]+cost[u][v]，则d[v]= d[u] + cost[u][v]，这样就满足d[v]-d[u]<=cost[u][v]”。

如此，如果要求最大值，把每个不等式变为标准x-y<=k的形式，然后建立一条从y到x的权值为k的边，求出最短路径即可；

如果要求最小值，把每个不等式变为标准x-y>=k的形式，然后建立一条从y到x的权值为k的边，求出最长路径即可；

注意：x-y<k,x-y<=k-1，大于同理；一般题目中除了明面上的约束，还会有一些隐藏的约束；由于差分约束系统常出现负权，故一般用SPFA；如果存在负环，则此约束系统不存在。

这里直接spfa会超时…说是要手写stack…用dijkstra+priority_queue也可，不过要用链式向前星来存储边。

链式向前星：http://blog.csdn.net/acdreamers/article/details/16902023

结构体：

struct edge
{
    int to;
    int cost;
    int next;
}eg[150010];
head[]数组一般初始化为-1,对于加边的add函数是这样的:
void add(int a,int b,int c)
{
    eg[top].cost=c;
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}

遍历时：

for(int i=head[id];i!=-1;i=eg[i].next)

POJ 1062

题意：

​ 有N个物品，每个物品都有自己的价格，但同时某些物品也可以由其他的（可能不止一个）替代品，这些替代品的价格比较“优惠”，问怎么样选取可以让你的花费最少来购买到物品1。

解题思路：

​ 建图只要设立一个原点即可，这里要注意题目条件是连间接接触都不行的，所以要枚举范围，而不是直接判断相邻的。

LightOJ 1074

题意：

​ 给定每条街的拥挤度p(x)，街a到街b的时间就是(p(b)-p(a))*3，求第一个点到第k个点的最短路，若无法到达或结果小于3，输出’?’。

解题思路：

​ 这里可能会出现负环的情况…这样的话while(!q.empty())会停不下来，判断个负环，然后dfs标记所有负环上的点，注意while(!q.empty())里面不要忘了if(cir[i])continue;

void dfs(int x)   //dfs标记环上的点
{
    cir[x]=true;
    for(int i=0;i<v[x].size();i++)
        if(!cir[v[x][i].to])
            dfs(v[x][i].to);
}

HDU 4725

题意：

​ 每个点放在一层，然后给了n个点，相邻的两层距离是固定的t，有额外m条边，然后求1到n的最短路径，如果没有则输出-1。

解题思路：

​ 难点在于建图。要将层抽象出来成为n个点（对应编号依次为n+1~n+n），然后层与层建边，点与点建边，层与在该层上的点建边（边长为0）（这时只要考虑该层进入这个点），点与相邻层建边（边长为c）（这时只要考虑从点出去），spfa+vector会TLE，用dijkstra+vector，或者spfa+链式前向星。

POJ 3169

题意：

​ 一些母牛按序号排成一条直线。有两种要求，A和B距离不得超过X，还有一种是C和D距离不得少于Y，问可能的最大距离。如果没有输出-1，如果可以随便排输出-2，否则输出最大的距离。

解题思路：

​ 差分约束。根据题目可得三个要求：s[i+1]-s[i]>=0;s[B]-s[A]<=D(ML);s[B]-s[A]>=D(MD)。看s[B]-s[A]<=D这个条件，因为最开始dis[i]初始化为INF，所以if(s[A]+D<s[B])s[B]=s[A]+D，是不是觉得这个条件很眼熟？就是最短路松弛的条件呀…所以就是最短路啦…也就是题目要求的最长…建边即可(A,B,D)，这样子一来，也可以把其他条件变一变，也可以变成这个样子来建边，s[A]-s[B]<=-D，建边(B,A,-D)，s[i]-s[i+1]<=0，建边(i+1,i,0)，建好图就跑一下spfa。如果出现负环，则说明无解，因为可以一直松弛下去，如果dis[i]==INF，就相当于1到i不连通，没有约束，则说明可以是任意解。

POJ 4370

题意：

​ 一个n*n的01矩阵，满足以下条件

X12+X13+…X1n=1
X1n+X2n+…Xn-1n=1
for each i (1<i<n), satisfies ∑Xki (1<=k<=n)=∑Xij (1<=j<=n).

另给出一个矩阵C，求∑Cij*Xij(1<=i,j<=n)的最小值。

解题思路：

​ 每个Xij都可以看做是一条路，X12+X13+……+X1n=1说明1的出度是1，X1n+X2n+……+Xn-1n=1说明n的入度是1，Xki(1<=k<=n) = Xij(1<=j<=n)说明其他点的入度等于出度，定一个超级原点和一个超级汇点，Xij=1的就是要选的那条路，这里跑一下1~n的最短路即可，但是，还要考虑一种情况，题没有说1的入度和n的出度情况，所以，可能存在1号点经过其它点成环，n号点经过其它点成环，这两个环的花费之和的情况，那么怎么求1或者n的最小花费环呢？可以直接搜索，也可以在跑最短路的时候先别把起始点入队，把起始点连接的所有点入队，这样跑完之后，到起始点的最短距离就是最小环了。

最短路中dijkstra最终所有最短路走的边，可以根据每次标记d[i]:这个点紧连的那条边的编号来得到。