[BZOJ1975][Sdoi2010]魔法猪学院（k短路）

题目描述

传送门

题解

这道题实际上就是要求出最短路、次短路…看能够承受多少
用A*算法找k短路即可

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define N 5003
#define E 200003

int n,m,s,t,size;
double k;
int tot,point[N],nxt[E],v[E],_tot,_point[N],_nxt[E],_v[E];double c[E],_c[E];
double dis[N];bool vis[N];
struct data
{
int x;double g;
bool operator < (const data &a) const
    {
return g+dis[x]>a.g+dis[a.x];
    }
};

void add(int x,int y,double z)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
    ++_tot; _nxt[_tot]=_point[y]; _point[y]=_tot; _v[_tot]=x; _c[_tot]=z;
}
void spfa()
{
queue <int> q;
memset(dis,127,sizeof(dis));
    dis[t]=0;vis[t]=1;q.push(t);
while (!q.empty())
    {
int now=q.front();q.pop();
        vis[now]=0;
for (int i=_point[now];i;i=_nxt[i])
if (dis[_v[i]]>dis[now]+_c[i])
            {
                dis[_v[i]]=dis[now]+_c[i];
if (!vis[_v[i]]) vis[_v[i]]=1,q.push(_v[i]);
            }
    }
}
void Astar()
{
    priority_queue <data> q;
    q.push((data){s,0});
while (!q.empty())
    {
        data now=q.top();q.pop();
if (now.x==t)
        {
if (now.g<k) k-=now.g,++size;
else return;
continue;
        }
for (int i=point[now.x];i;i=nxt[i])
            q.push((data){v[i],now.g+c[i]});
    }
}
int main()
{
    freopen("input.in","r",stdin);
scanf("%d%d%lf",&n,&m,&k);
for (int i=1;i<=m;++i)
    {
int x,y;double z;
scanf("%d%d%lf",&x,&y,&z);
        add(x,y,z);
    }
    s=1,t=n;
    spfa();
    Astar();
printf("%d\n",size);
}