紧急求助!!!
  • 板块P1807 最长路
  • 楼主ZYH_juruo
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/8/22 17:23
  • 上次更新2023/10/27 14:08:43
查看原帖
紧急求助!!!
565903
ZYH_juruo楼主2022/8/22 17:23

本蒟蒻代码能力不行,跪求大佬调代码。

#include<bits/stdc++.h>
#define inf -0x3f3f3f3f
#define int long long
using namespace std;
const int maxm=500050;
const int maxn=100010;
priority_queue<pair<int,int> > q;
int n,m,u,v,w;
struct node{
	int to;
	int w;
	int nxt;
}edge[maxm];
int tot,head[maxm];
long long dis[maxn];
int vis[maxn];
void add(int u,int v,int w)
{
	edge[++tot].to=v;
	edge[tot].w=w;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
signed main()
{
	memset(vis,0,sizeof(vis));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		dis[i]=inf;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x]==1) continue;
		vis[x]=1;
		for(int i=head[x];i!=0;i=edge[i].nxt)
		{
			if(dis[edge[i].to]<dis[x]+edge[i].w){
				dis[edge[i].to]=dis[x]+edge[i].w;
				q.push(make_pair(dis[edge[i].to],edge[i].to));
			}	
		}
	}

	if(dis[n]<=inf)
		cout<<"-1"<<endl;
	else
		cout<<dis[n]<<endl;
	return 0;
}
2022/8/22 17:23
加载中...