跑两遍spfA会T?
查看原帖
跑两遍spfA会T?
523541
Onana_in_XMFLS楼主2021/10/11 11:08
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const int INF = 2147483647;
const int S = 1e4+5;
int n,m,tot;
int head[S],ver[S],edge[S],Next[S],dis[S],vis[S],v[S];
queue <int> q;
inline void add(int x,int y,int z)
{ver[++tot] = y,edge[tot] = z,Next[tot] = head[x],head[x] = tot;}
inline void spfA(int s)
{
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(v,0,sizeof(v));
	dis[s] = 0; 
	vis[s] = 1;
	++v[s];
	q.push(s);
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		vis[x] = 0;
		if(v[x] > n) {puts("Forever love");exit(0);}
		for(int i = head[x];i;i = Next[i])
		{
			int y = ver[i],z = edge[i];
			if(dis[y] > dis[x]+z)
			{
				dis[y] = dis[x]+z;
				if(!vis[y]) {q.push(y);vis[y] = 1;}
			}
		}
	}
}
inline LL read()
{
	LL x=0,f=1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
	return f*x;
}
int main(int argc,char *argv[])
{ 
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);	
	n = read(),m = read();
	while(m--)
	{
		int u = read(),v = read(),w = read();
		add(u,v,-w);
	}
	spfA(1);
	int ans = dis[n];
	spfA(n);
	ans = min(ans,dis[1]);
	printf("%d\n",ans);
	//printf("Tide used = %.0lf.ds\n",((double)clock()/(double)CLOCKS_PER_SEC) * 1000.0);
	return 0;
}  

RT,T了7个点……

2021/10/11 11:08
加载中...