第一题

用堆维护。

#include 
     
      #include 
      
       #include 
       
        int n,i,f[400000],g[2][200000],j=0,k[400000];int l,r;bool cho;struct pn{	int l,r,n;};bool operator<(pn a,pn b){	return a.n>b.n;}std::priority_queue
        
          q;pn as,as1,as2;int main(){	freopen("minval.in","r",stdin);	freopen("minval.out","w",stdout);	scanf("%d",&n);	for(i=0;i
        
       
      
     

第二题

连通性判定+二分图

#include 
     
      #include 
      
       int f[200000],d,i,j,m,n,s,t,tt,a,b,pl,h[200000];int q[200000],qh,qt;bool f2;struct edge{	int t,n;} edges[2000000];inline void addedge(int f,int t){	edges[++pl].n=h[f];	edges[ pl ].t= t  ;	h[f]=pl;} int main(){	freopen("catch.in","r",stdin);	freopen("catch.out","w",stdout);	scanf("%d",&tt);	while(tt--){		++j;		memset(f,0,sizeof f);		memset(h,0,sizeof h);		pl=0;		qh=qt=0;		scanf("%d%d%d",&n,&m,&s);		for(i=0;i
      
     

第三題：二分答案加判定

#include 
     
      #include 
      
       struct edge{	int t,n,w;} e[300000];int h[20000],pl;inline void addedge(int f,int t,int w){	e[++pl].t=t;	e[pl].n=h[f];	e[pl].w=w;	h[f]=pl;}int n,m,u,v,s,i,j,k;int left,right,mid,ans;int cost[20000];int q[100000],qh,qt;bool iq[20000];int f[20000];int ka,kb,ww;int v0,v1,e0;void spfa(int mma){	memset(f,-1,sizeof f);	memset(iq,0,sizeof iq);	qh=qt=0;	q[qt++]=u;	f[u]=0;	while(qh!=qt){		v0=q[qh++];		iq[v0]=false;		for(e0=h[v0];e0;e0=e[e0].n){			v1=e[e0].t;			if(cost[v1]>mma) continue;			if(f[v1]==-1 || f[v1] > f[v0] + e[e0].w){				f[v1] = f[v0] + e[e0].w;				if(!iq[v1]){					iq[v1]=true;					q[qt++]=v1;				}			}		}	}}int main(){	freopen("cost.in","r",stdin);	freopen("cost.out","w",stdout);	scanf("%d%d%d%d%d",&n,&m,&u,&v,&s);	left=0x7fffffff;	for(i=1;i<=n;++i){		scanf("%d",cost+i);		if(cost[i]
       
        right) right=cost[i];	}	for(i=1;i<=m;++i){		scanf("%d%d%d",&ka,&kb,&ww);		addedge(ka,kb,ww);		addedge(kb,ka,ww);	}	spfa(right);	if(f[v]==-1 || f[v] > s){		printf("-1\n");		return 0;	}	while(left<=right){		mid=(left+right)/2;		spfa(mid);		if( f[v] == -1 || f[v] > s ){			left=mid+1;		}else{			right=mid-1;			ans=mid;		}	}	printf("%d\n",ans);	return 0;}
       
      
     

更新：修復了exceed 32bit int的bug

#include 
     
      #include 
      
       struct edge{	int t,n,w;} e[300000];long long h[20000],pl;inline void addedge(int f,int t,int w){	e[++pl].t=t;	e[pl].n=h[f];	e[pl].w=w;	h[f]=pl;}long long n,m,u,v,s,i,j,k;long long left,right,mid,ans;long long cost[20000];long long q[100000],qh,qt;bool iq[20000];long long f[20000];long long ka,kb,ww;long long v0,v1,e0;void spfa(int mma){	memset(f,-1,sizeof f);	memset(iq,0,sizeof iq);	qh=qt=0;	q[qt++]=u;	f[u]=0;	while(qh!=qt){		v0=q[qh++];		iq[v0]=false;		for(e0=h[v0];e0;e0=e[e0].n){			v1=e[e0].t;			if(cost[v1]>mma) continue;			if(f[v1]==-1 || f[v1] > f[v0] + e[e0].w){				f[v1] = f[v0] + e[e0].w;				if(!iq[v1]){					iq[v1]=true;					q[qt++]=v1;				}			}		}	}}int main(){	freopen("cost.in","r",stdin);	freopen("cost.out","w",stdout);	scanf("%lld%lld%lld%lld%lld",&n,&m,&u,&v,&s);	left=0x7fffffff;	for(i=1;i<=n;++i){		scanf("%lld",cost+i);		if(cost[i]
       
        right) right=cost[i];	}	for(i=1;i<=m;++i){		scanf("%lld%lld%lld",&ka,&kb,&ww);		addedge(ka,kb,ww);		addedge(kb,ka,ww);	}	spfa(right);	if(f[v]==-1 || f[v] > s){		printf("-1\n");		return 0;	}	while(left<=right){		mid=(left+right)/2;		spfa(mid);		if( f[v] == -1 || f[v] > s ){			left=mid+1;		}else{			right=mid-1;			ans=mid;		}	}	printf("%lld\n",ans);	return 0;}