解题报告 P4568 [JLOI2011]飞行路线

题目内容

P4568

大意：n 个城市 m 条航线，可以免费掉最多 k 条航线，求从 s 到 t 的最少花费。

解题思路

分层图最短路模板，将图分成 k+1 层处理，每层之间照常连航线的边，跨层连免费航线，跑一遍最短路然后统计答案就可以了。每往下一层就相当于免费搭了一次飞机。

spfa 会被卡

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e4+5;

struct edge
{
    int to,dist;
    edge(){}
    edge(int b,int c)
    {
        to=b,dist=c;
    }
};

vector<edge> g[maxn*11];
int n,m,k,s,t;
queue<int> q;
bool vis[maxn*11];//记得空间开够
int d[maxn*11];

void ins(int u,int v,int w)
{
    g[u].push_back(edge(v,w));
    return;
}

void dij()//跑dij
{
    priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
    memset(d,0x3f3f3f3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g[now])
            {
                if(d[e.to]>d[now]+e.dist)
                {
                    d[e.to]=d[now]+e.dist;
                    q.push(make_pair(d[e.to],e.to));
                }
            }
        }
    }
    return;
}

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    scanf("%d %d",&s,&t);
    register int a,b,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        for(int j=0;j<=k;j++)//每层中间连
        {
            ins(a+n*j,b+n*j,c);
            ins(b+n*j,a+n*j,c);
            if(j<k)//跨层连
            {
                ins(a+n*j,b+(j+1)*n,0);
                ins(b+n*j,a+(j+1)*n,0);
            }
        }
    }
    dij();
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;i++)
        ans=min(ans,d[i*n+t]);
    printf("%d\n",ans);
    return 0;
}