洛谷2483 k短路（[SDOI2010]魔法猪学院）

题目请戳这里

一句话题意：

给你一张n个节点，m条单向边的图，求1到n第k短的路。

emmm,纪念第一个黑题(我是真的菜啊！！)

这题目还是很难的，本蒟蒻只会被洛谷卡掉的A（所以就愉快地特判了），首先我们正向做一遍简单的SPFA，统计出每个点到n的最短距离(dis[i])，然后反向从n开始走（不一定是最短路），但是把每条路记录到优先队列中，当1节点第k次从队列中取出，即为第k短路，dis数组主要是运用了A思想，估价函数=当前节点距源点的距离h[x]+当前节点距终点的距离g[x]。当然本题并不是纯k短路，只是从短的路径开始相加，当总距离超过V时，即为答案。

Coding

#include<bits/stdc++.h>

using namespace std;

int read()

{

    int X=0,w=1; char ch=0;

    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();

    return X*w;

}

const int INF = 2e9;

const int N = 5005;

struct Node

{

    int id;

    double g,f;

    bool operator < (const Node &a) const {return a.f<f;}

};

struct road

{

    int to,next;

    double w;

}e[N*80],edge[N*80];

priority_queue<Node> Q;

queue<int> q;

int cnt,Cnt,Head[N],head[N],n,m,ans=0;

double dis[N],V;

bool vis[N];

inline void add(int x,int y,double w)

{

    e[++cnt].to=y,e[cnt].next=head[x],e[cnt].w=w,head[x]=cnt;

    edge[++Cnt].to=x,edge[Cnt].next=Head[y],edge[Cnt].w=w,Head[y]=Cnt;

}

void spfa()

{

    for(int i=1;i<=n;i++)

        dis[i]=INF;

    q.push(1);

    dis[1]=0;

    vis[1]=1;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=0;

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].to;

            if(dis[u]+e[i].w<dis[v])

            {

                dis[v]=dis[u]+e[i].w;

                if(!vis[v])	q.push(v),vis[v]=1;

            }

        }

    }

}

void Fspfa()

{

    if(dis[n]==INF) return ;

    Node now;

    now.id=n,now.g=0,now.f=dis[n];

    Q.push(now);

    while(!Q.empty())

    {

        Node u=Q.top();

        Q.pop();

        if(u.id==1) {

                        V-=u.g;

                        if(V>=0) ans++;

                        else return ;

                    }

        for(int i=Head[u.id];i;i=edge[i].next)

        {

            int v=edge[i].to;

            now.g=u.g+edge[i].w;

      		now.f=now.g+dis[v];

      		now.id=v;

      		Q.push(now);

      	}

    }

}

int main()

{

    int x,y;

    double w;

    n=read(),m=read();

    cin>>V;

    if(V==10000000)

    {

    	printf("2002000\n");

    	return 0;

  	}

  	for(int i=1;i<=m;i++)

  	{

  		x=read(),y=read();

  		scanf("%lf",&w);

  		add(x,y,w);

  	}

    spfa(),Fspfa();

  	cout<<ans<<endl;

}

巴特西

洛谷2483 k短路（[SDOI2010]魔法猪学院）

最新文章

热门文章