90分求助
查看原帖
90分求助
363807
Hamer_sans楼主2021/10/2 21:04

第十个点错了

代码如下

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int sum=0,h=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') h=-1;ch=getchar();}
	while(isdigit(ch)) sum=sum*10+ch-'0',ch=getchar();
	return sum*h;
}
const int N=2e4+5;
int ver[N],head[N],ne[N],edge[N],tot;
int n,m;
int dist[N];
bool vis[N];
void add(int x,int y,int z){
	ver[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
	edge[tot]=z;
	return;
}
int spfa(){
	queue<int> q;
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	vis[1]=1;
	q.push(1);
	int cnt=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		if(cnt>n) return 0;
		for(register int i=head[x];i;i=ne[i]){
			int y=ver[i];
			if(dist[y]>dist[x]+edge[i]){
				dist[y]=dist[x]+edge[i];
				++cnt;
				if(!vis[y]){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	return dist[n];
}
int main(){
	n=read(),m=read();
	for(register int i=1;i<=m;++i){
		int x,y,z;
		x=read(),y=read(),z=read();
		add(x,y,-z);
	}
	int p=spfa();
	if(!p) puts("Forever love");
	else printf("%d",p);
	return 0;
}
2021/10/2 21:04
加载中...