#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=105;
int n,m,s;
double cost[maxn][maxn],dist[maxn],d[maxn][maxn],v;
int vis[maxn][maxn];
int main()
{	scanf("%d %d %d %lf\n",&n,&m,&s,&v);
	memset(dist,0,sizeof(dist));
	memset(vis,0,sizeof(vis));
	for (int i=1; i<=m; ++i)
	{
		int x,y;
		scanf("%d %d",&x,&y); 
		scanf("%lf %lf %lf %lf\n",&d[x][y],&cost[x][y],&d[y][x],&cost[y][x]);
		vis[x][y]=1; vis[y][x]=1;
	}
	int vis1[maxn];
	int sum[maxn];
	memset(sum,0,sizeof(sum));
	memset(vis1,0,sizeof(vis1));
    int head=0,tail=1;
	int q[maxn]; 
	memset(q,0,sizeof(q));	
	q[1]=s; vis1[s]=1; dist[s]=v; 
    while (head<tail)
    {
    	head++;
    	int x=q[head];
    	vis1[x]=0;
    	sum[x]++;
    	if (sum[x]>n) break;
    	for (int i=1; i<=n; ++i)
    	 if (vis[x][i] && dist[i]<(dist[x]-cost[x][i])*d[x][i])
    	  {
    	  	dist[i]=(dist[x]-cost[x][i])*d[x][i];
    	    if (!vis1[i])
    	    {
    	    	tail++;
    	    	q[tail]=i;
    	    	vis1[i]=1;
			}
		  }
	}
	if (dist[s]>v) printf("%s\n","YES");
	          else printf("%s\n","NO");
}

• Re:不知道WA了多少次了，求大神 (2598) fengyucan 2019-07-29 21:55:39