POJ 1860 Currency Exchange 毫无优化的bellman_ford跑了16Ms，spfa老是WA。。

olnm

　　题目链接： http://poj.org/problem?id=1860
　　找正环，找最长路，水题，WA了两天了。。





#include <stdio.h>
#include <string.h>
struct Edge
{
int u, v;
double r, c;
}edge[210];
int rear, n, m, s;
double v, dist[110];
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[edge[j].v] < (dist[edge[j].u]-edge[j].c) * edge[j].r)
dist[edge[j].v] = (dist[edge[j].u]-edge[j].c) * edge[j].r;
for(int j = 0; j < rear; j++)
if(dist[edge[j].v] < (dist[edge[j].u]-edge[j].c) * edge[j].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[rear++] = (struct Edge){a, b, rab, cab};
edge[rear++] = (struct Edge){b, a, rba, cba};
}
printf("%s\n", bellman_ford() ? "YES" : "NO");
}
return 0;
}
View Code