#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1009 ;
vector<int> G[N];
double mp[N][N],dis[N],co[N][N];
bool vis[N];
bool flag = false ;
void f(int n){
	int h = n ;
	while(h--)
	{
		int max_p ;
		double max_d = 0 ;
		for(int i = 1 ; i <= n ; ++ i)
		{
			if(!vis[i] && dis[i] > max_d ){
				max_d = dis[max_p = i];
			}
		}
		vis[max_p] = true ;
		int u = max_p ;
		for(int i = 0 ; i< G[u].size() ;++ i ){
			int v = G[u][i];
			if(vis[v]) continue;
			dis[v] = max(dis[v],(dis[u]-co[u][v])*mp[u][v]);
		}
	}
	return ; 
}
void g (int n){
	for(int i = 1 ; i <= n ; ++ i){
		for(int j = 1 ; j <= n ; ++ j)
		{
			if(i==j) continue ;
			if(dis[j] < (dis[i]-co[i][j])*mp[i][j] )
			{
				flag = true ;
				return ;
			}
		}
	}
	return ;
}
int main (){
	int n,m,s;
	double v ;
	scanf("%d%d%d%lf",&n,&m,&s,&v);
	for(int i = 1 ; i <= m ; ++ i){
		int a,b;
		double e1,c1,e2,c2;
		scanf("%d%d%lf%lf%lf%lf",&a,&b,&e1,&c1,&e2,&c2);
		mp[a][b] = e1,mp[b][a] = e2; 
		co[a][b] = c1,co[b][a] = c2;
		G[a].push_back(b),G[b].push_back(a);
	}
	dis[s] = v ; 
	//vis[s] = true ;
	f(n);
	g(n);
	if(flag) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0 ;
}

• Re:不明白为什么选G++ 会RE 而C++就AC了 (1400) Cyansky 2022-08-28 21:38:34