P2939 改造路

裸地分层图最短路

培训的时候考到过

但是……

我考试的时候写了个基本没有的树状数组优化。然后顺利的被卡到了70分（裸的spfa都有80分qwq）

伤心

然后今天又重新拿堆优化dij搞了一波。一发ac真开心qwq

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<queue>

#include<cstring>

using std::min;

using std::priority_queue;

const int maxn=20100;

int dis[maxn][21],head[maxn],tail;

bool Get[maxn][21];

int n,m,k;

struct node

{

	int point;

	int weight;

	int nxt;

};

struct Data//优先队列使用的结构体

{

    int p,k;

    int val;

    Data (int a=0,int b=0,int c=0){ p=a,k=b,val=c; }

    bool operator < (const Data &A)const

    {

        return val>A.val;

    }

};

node line[101000];

int read()

{

	int res=0;char c=getchar();

	while(c>'9'||c<'0')	c=getchar();

	while(c>='0'&&c<='9')

	{

		res=res*10+c-'0';

		c=getchar();

	}

	return res;

}

void add(int x,int y,int z)

{

	line[++tail].point=y;

	line[tail].nxt=head[x];

	line[tail].weight=z;

	head[x]=tail;

}

void bfs()

{

    priority_queue<Data>q;

    memset(dis,127,sizeof(dis));

    dis[1][0]=0;

    q.push(Data(1,0,0));//起点

    int tot=0;

    while(!q.empty())

    {

        Data pas=q.top();q.pop();

    	//printf("\t%d\t%d\t%d\n",pas.p,pas.k,pas.val);

        while(Get[pas.p][pas.k])//这个状态已经到达了

        {

            pas=q.top();

            q.pop();

        }

        int P=pas.p,K=pas.k;

        Get[P][K]=true;

        if(P==n)//终点状态

        {

        	printf("%d",pas.val);

        	break;

		}

        for(int i=head[P];i;i=line[i].nxt)

        {

            int v=line[i].point;

            if(K+1<=k&&dis[v][K+1]>dis[P][K])//使用边权无效化

            {

                dis[v][K+1]=dis[P][K];

                Data nxt(v,K+1,dis[v][K+1]);

                q.push(nxt);

            }

            if(dis[v][K]>dis[P][K]+line[i].weight)//不消除边权

            {

                dis[v][K]=dis[P][K]+line[i].weight;

                Data nxt(v,K,dis[v][K]);

                q.push(nxt);

            }

        }

    }

}

int main()

{

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

        scanf("%d%d%d",&n,&m,&k);

	int a,b,c;

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

	{

		//int a=read(),b=read(),c=read();

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);add(b,a,c);

	}

	bfs();

}

/*

5 6 1

1 2 2

1 3 4

2 4 3

3 4 1

3 5 6

4 5 2

*/

巴特西

P2939 改造路

但是……

最新文章

热门文章