分层图

先看一道裸题

分层图的典型应用，有K条免费边，除了原图外再建K层图。然后对于从每个点出的每一条边，连一条从此点到这条边终点所对应的上一层的点，边权为零，从一层到下一层相当于走了一条免费边。由于不需要走完所有的免费边，所以应取所有层的终点的最短路的最小值。

如图所示：
这里只画出来0号节点的免费边

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f
#define MAXN 1000010
#define MAXM 5010

inline int read()
{
    int x =  0,ff = 1;char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') ff = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * ff;
}

int n,m,k,dis[MAXN],vis[MAXN],ans = INF;
int lin[MAXN],tot = 0;
struct edge
{
    int y,v,next;
}e[MAXN];

void add(int xx,int yy,int vv)
{
    e[++tot].y = yy;
    e[tot].v = vv;
    e[tot].next = lin[xx];
    lin[xx] = tot;
}

void SPFA()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    queue < int > q;
    q.push(1); dis[1] = 0; vis[1] = true;
    while(!q.empty())
    {
        int x = q.front(); q.pop(); vis[x] = false;
        for(int i = lin[x],y;i;i = e[i].next)
        {
            if(dis[y = e[i].y] > dis[x] + e[i].v)
            {
                dis[y] = dis[x] + e[i].v;
                if(!vis[y])
                {
                    vis[y] = true;
                    q.push(y);
                }
            }
        }
    }
}

int main()
{
    n = read(); m = read(); k = read();
    for(int i = 1;i <= m;++i)
    {
        int x,y,v;
        x = read(); y = read(); v = read();
        for(int j = 0;j <= k;++j)
        {
            add(x + n * j,y + n * j,v);
            add(y + n * j,x + n * j,v);
            if(j != k)
            {
                add(x + n * j,y + n * (j + 1),0);
                add(y + n * j,x + n * (j + 1),0);
            }
        }
    }
    SPFA();
    for(int i = 1;i <= (k + 1);++i)
    ans = min(ans,dis[n * i]);
    printf("%d
",ans);
    system("PAUSE");
    return 0;
}