RE 55分求调!
  • 板块P6822 [PA2012] Tax
  • 楼主rq_kyz
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/1/21 19:00
  • 上次更新2024/1/21 21:06:30
查看原帖
RE 55分求调!
750233
rq_kyz楼主2024/1/21 19:00

RT,错误信息:

Runtime Error.

Received signal 11: Segmentation fault with invalid memory reference.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct s1{
	ll i,l;
};
vector<s1> a[100001];
bool cmp(s1 num1,s1 num2){
	return num1.l<num2.l;
}
struct s2{
	ll x,y,l;
}b[200001];
ll last[800001];
struct s3{
	ll t,to,l;
}nxet[2000001];
ll cd=0;
void lj(ll x,ll y,ll l){
	nxet[++cd].t=last[x];
	nxet[cd].to=y;
	nxet[cd].l=l;
	last[x]=cd;
}
ll dis[800001];
bool vis[800001];
struct s4{
	ll x,l;
}h[2000001];
ll len=1;
bool f(s4 num1,s4 num2){
	return num1.l>num2.l;
}
void dijkstra(ll s){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	h[0]={s,0};
	while(len){
		ll x=h[0].x;
		pop_heap(h,h+len,f);
		len--;
		if(vis[x])
			continue;
		vis[x]=1;
		for(ll j=last[x];j;j=nxet[j].t){
			ll y=nxet[j].to;
			if(dis[y]>dis[x]+nxet[j].l){
				dis[y]=dis[x]+nxet[j].l;
				h[len].x=y;
				h[len++].l=dis[y];
				push_heap(h,h+len,f);
			}
		}
	}
}
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld%lld",&b[i].x,&b[i].y,&b[i].l);
		if(b[i].x>b[i].y)
			b[i].x^=b[i].y^=b[i].x^=b[i].y;
		a[b[i].x].push_back({i,b[i].l});
		a[b[i].y].push_back({i,b[i].l});
	}
	for(ll i=1;i<=n;i++){
		sort(a[i].begin(),a[i].end(),cmp);
		ll x,y;
		if(b[a[i][0].i].x==i){
			x=4*a[i][0].i-3;
			y=4*a[i][0].i-2;
		} else {
			x=4*a[i][0].i-1;
			y=4*a[i][0].i;
		}
		lj(x,y,a[i][0].l);
		lj(y,x,0);
		ll y0=y;
		for(ll j=1;j<a[i].size();j++){
			if(b[a[i][j].i].x==i){
				x=4*a[i][j].i-3;
				y=4*a[i][j].i-2;
			} else {
				x=4*a[i][j].i-1;
				y=4*a[i][j].i;
			}
			lj(y0,y,a[i][j].l-a[i][j-1].l);
			lj(y,y0,0);
			lj(x,y,a[i][j].l);
			lj(y,x,0);
			y0=y;
		}
	}
	for(ll i=1;i<=m;i++){
		lj(4*i-2,4*i-1,0);
		lj(4*i,4*i-3,0);
	}
	dijkstra(4*a[1][0].i-3);
	ll ans=0x3f3f3f3f3f3f3f3f;
	for(ll i=0;i<a[n].size();i++)
		ans=min(ans,dis[4*a[n][i].i]);
	printf("%lld",ans);
    return 0;
}
2024/1/21 19:00
加载中...