Dijkstra 86pts WA#6#7 求助
查看原帖
Dijkstra 86pts WA#6#7 求助
342036
Star_V楼主2023/11/14 10:43
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+500;
const int M=1e7+500;
int n,t;
struct node
{
	int x,y;
}a[N];
int head[N],cnt;
struct edge
{
	int from;
	int to;
	int nex;
	int len;
}e[M];
bool cmp(node a,node b)
{
	return a.x<b.x;
}
void add(int x,int y,int z)
{
	e[++cnt]=(edge)
	{
		x,y,head[x],z
	};
	head[x]=cnt;
}
struct dato
{
    int dot,len;	
};
bool operator < (dato x,dato y)
{
	return x.len>y.len;
}
int dis[N];
int vis[N];
priority_queue<dato>q;
void dij()
{
	q.push((dato){1,0});
	while(!q.empty())
	{
		int u=q.top().dot;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nex)
		{
			int v=e[i].to;
		    if(dis[v]>dis[u]+e[i].len)
		    {
		    	dis[v]=dis[u]+e[i].len;
		    	q.push((dato){v,dis[v]});
		    }
		}
	}
}
int main()
{
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=t;i>=1;i--) add(i,i-1,0);
	for(int i=1;i<=n;i++)
	{
		int l,r;
		l=a[i].x; r=a[i].y;
		add(l-1,r,1);
	}
	for(int i=0;i<=t;i++) dis[i]=1e9;
	dis[1]=0;
    dij();
	if(dis[t]==1e9) cout<<-1;
	else cout<<dis[t];
	return 0;
}
2023/11/14 10:43
加载中...