SSL 2677_飞行_spfa

lzusa 发布于 2017-08-10 3 次阅读

题目描述

有n个城市，编号为0到n-1。小B想从城市s到城市t。他们选择了一家航空公司，这家公司有m种航线，每种航线连接了两个不同的城市。看在小B是个妹子的份上，航空公司的老总给了小B一点优惠：小B可以免费在最多k种航线上搭乘飞机。问小B最小花费是多少。

 

思路

在普通的spfa上多加一维， state[i][j]表示从起点到i点用了j此免费的最小花费，转移显然

在spfa时多枚举一个j即可

#include 
#include 
#include 
#include 
using namespace std;
#define maxn 100001
#define maxm 500001
#define INF 0x3f3f3f3f
#define min(x, y) (x) < (y) ? (x) : (y)
#define fill(x, y) memset(x, y, sizeof(x))
struct edge
{
    int to, w, next;
}e[maxm * 2];
int ls[maxm * 2], n, m, k, s, t, state[maxn][20], exits[maxn]; 
int spfa()
{
    fill(state, INF);
    queue t;
    t.push(s);
    exits[s] = 1;
    for (int i = 0; i <= k; i++)
        state[s][i] = 0;
    while (!t.empty())
    {
        int now = t.front();
        t.pop();
        for (int i = ls[now]; i; i = e[i].next)
            for (int j = 0; j <= k; j++)
            {
                if (state[now][j] + e[i].w < state[e[i].to][j])
                {
                    state[e[i].to][j] = state[now][j] + e[i].w;
                    if (!exits[e[i].to])
                    {
                        exits[e[i].to] = 1;
                        t.push(e[i].to);
                    }
                }
                if (state[now][j] < state[e[i].to][j + 1] && j + 1 <= k)
                {
                    state[e[i].to][j + 1] = state[now][j];
                    if (!exits[e[i].to])
                    {
                        exits[e[i].to] = 1;
                        t.push(e[i].to);
                    }
                }
            }
        exits[now] = 0;
    }
}
int main()
{
    scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
    int l = 0;
    for (int i = 1;i <=m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        e[++l] = (edge) {y, z, ls[x]};
        ls[x] = l;
        e[++l] = (edge) {x, z, ls[y]};
        ls[y] = l;
    }
    spfa();
    int ans = INF;
    for (int i = 0; i <= k; i++)
    {
        ans = min(ans, state[t][i]);
    }
    printf("%d\n", ans);
}

 

]]>