POJ 1860 Currency Exchange 毫无优化的bellman_ford跑了16Ms，spfa老是WA。。
题目链接： http://poj.org/problem?id=1860找正环，找最长路，水题，WA了两天了。。
#include <stdio.h>
#include <string.h>
struct Edge
{
int u, v;
double r, c;
}edge;
int rear, n, m, s;
double v, dist;
bool bellman_ford()
{
memset(dist, 0, sizeof(dist));
dist = v;
for(int i = 1; i < n; i++)
for(int j = 0; j < rear; j++)
if(dist.v] < (dist.u]-edge.c) * edge.r)
dist.v] = (dist.u]-edge.c) * edge.r;
for(int j = 0; j < rear; j++)
if(dist.v] < (dist.u]-edge.c) * edge.r)
return 1;
return 0;
}
int main()
{
int a, b;
double rab, cab, rba, cba;
while(scanf("%d %d %d %lf", &n, &m, &s, &v) != EOF)
{
rear = 0;
while(m--)
{
scanf("%d %d %lf %lf %lf %lf", &a, &b, &rab, &cab, &rba, &cba);
edge = (struct Edge){a, b, rab, cab};
edge = (struct Edge){b, a, rba, cba};
}
printf("%s\n", bellman_ford() ? "YES" : "NO");
}
return 0;
}
View Code
页:
[1]