邻接表保存最大边怎么存
  • 板块P1807 最长路
  • 楼主BVVD_FM
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/4/20 13:19
  • 上次更新2023/10/23 18:00:01
查看原帖
邻接表保存最大边怎么存
808332
BVVD_FM楼主2023/4/20 13:19

大佬求助,有两点之间有多条边时邻接表要保存最大边值怎么存?

#include<bits/stdc++.h>
using namespace std;
#define LF printf(" ");
#define NF printf("\n");
unsigned const int N=1505;
unsigned const int M=5e4+10;
int n,m;
int head[N],nxt[M],ver[N],idx=1,wi[M];
int level[N],vis[N];
int q[M],front=0,rear=0;
inline void add(int x,int y,int z){
	ver[idx]=y;
	wi[idx]=z;
	nxt[idx]=head[x];
	head[x]=idx++; 
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}
void init(){
	memset(head,-1,sizeof head);
	memset(level,-1,sizeof level);
}
void BFS(int root){
	q[rear++]=root;
	vis[root]=1;
	level[root]=0;
	while(front<rear){
		int x=q[front];
		front++;
		for(int i=head[x];~i;i=nxt[i]){
			int v=ver[i];
			int w=wi[i];
			vis[v]=1;
			q[rear++]=v;
			if(level[v]<level[x]+w){
				level[v]=level[x]+w;
			}
		}
	}
}
int main(){
	n=read(),m=read();
	init();
	for(int i=1;i<=m;i++){
		int x,y,z;
		x=read(),y=read(),z=read();
		add(x,y,z);
	}
	BFS(1);
	write(level[n]);
	return 0;
}
/*
3 3
1 3 10
1 2 1
2 3 10

out
:11
*/

过不去5,6样例

2023/4/20 13:19
加载中...