求调(55分)
查看原帖
求调(55分)
878275
taskkill_same楼主2024/8/16 10:02

大佬们帮帮我!

#include<iostream>
#include<cstring>
using namespace std;
const int N=2000,M=5e4+1;
int allow[10000001];
int head[N];
int hd=0,tl=0;
int tot=0;
int p_s,p_e,e_w;
struct edge{
	int ver;
	int next;
	int edge;
}E[M];
bool flag[N];
int dist[N];
int n,m;
int x,y,z;
void spfa(){
	for(int i=1;i<=n;i++){
		dist[i]=-1;
	}
	memset(flag,0,sizeof(flag));
	dist[1]=0;
	flag[1]=1;
	hd++;
	allow[hd]=1;
	while(tl<=hd+1){
		tl++;
		x=allow[tl];
		flag[x]=0;
		for(int i=head[x];i;i=E[i].next){
			y=E[i].ver;
			z=E[i].edge;
			if(dist[y]<dist[x]+z){
				dist[y]=dist[x]+z;
			}
			if(flag[y]==0){
				hd++;
				allow[hd]=y;
			}
			flag[y]=0;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>p_s>>p_e>>e_w;
		tot++;
		E[tot].edge=e_w;
		E[tot].ver=p_e;
		E[tot].next=head[p_s];
		head[p_s]=tot;
	}
	spfa();
	cout<<dist[n];
	return 0;
}
2024/8/16 10:02
加载中...