以下代码，若mian函数调用spfa会32msAC，floyd会100+msAC，不明白的是为何floyd中外层循环需要执行n*5次，我试了n+1(WA),n*2(WA),n*3(WA),n*5(AC),n*10(AC),n*50(AC),n*100(TLE)....
求解释，是不是用floyd有问题呢？这个5肯定没有什么含义，那么外层应该如何写呢？
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <iterator>
#include <list>
#include <algorithm>
#include <bitset>
#include <set>
#include <sstream>
#include <functional>
using namespace std;
const int N = 105;
int n,m;
int st;
double sum;
double r[N][N];
double c[N][N];
void input() {
	scanf("%d%d%d%lf",&n,&m,&st,&sum);
	--st;//第一个注意的地方，因为我做的是下标从0开始，题中是从1开始
	memset(r,0,sizeof(r));
	memset(c,0x3f,sizeof(c));//第二个注意的地方，如果初始化为0就可以随意换了
	for (int i=0; i<m; ++i) {
		int a,b;
		double rab,cab,rba,cba;
		scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
		r[a-1][b-1] = rab;
		c[a-1][b-1] = cab;
		r[b-1][a-1] = rba;
		c[b-1][a-1] = cba;
	}
}
bool floyd() {
	double d[N];
	memset(d, 0, sizeof(d));
	d[st] = sum;
	for (int i = 0; i < n; ++ i) {
		if ((d[st]-c[st][i])*r[st][i]>d[i]) {
			d[i] = (d[st]-c[st][i])*r[st][i];
		}
	}
	for (int k = 0; k < n*5; ++ k) {//此处为何需要乘以5才能过呢？疑惑中⋯⋯
		for (int i = 0; i < n; ++ i) {
			for (int j = 0; j < n; ++ j) {
				if ((d[i]-c[i][j])*r[i][j] > d[j]) {
					d[j] = (d[i]-c[i][j])*r[i][j];
				}
			}
		}
	}
	return d[st]>sum;
}
bool spfa() {
	double d[N];
	memset(d,0,sizeof(d));//第三个注意地方，除了起始，所有货币最大值的下限都要初始化为0
	d[st] = sum;
	bool v[N];
	memset(v, 0, sizeof(v));
	v[st] = 1;
	int cnt[N];
	memset(cnt, 0, sizeof(cnt));
	cnt[st] = 1;
	queue<int> que;
	que.push(st);
	while (!que.empty()) {
		int u = que.front(); que.pop(); v[u] = 0;
		for (int i = 0; i < n; ++ i) {
			double t = (d[u]-c[u][i])*r[u][i];//第四个注意的地方，无他，double————写int写习惯了，调了半天错，非常郁闷
			if (t > d[i]) {
				d[i]=t;
				if (!v[i]) {
					v[i]=1;
					if (++cnt[i]>n) {
						return 1;
					}
					que.push(i);
				}
			}
		}
	}
	return d[st]>sum;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("/Users/songzhipeng/Desktop/in.in","r",stdin);
	freopen("/Users/songzhipeng/Desktop/out.out", "w", stdout);
#endif
	input();
	printf("%s",floyd()?"YES":"NO");
	return 0;
}

• Re:floyd为何外层循环需要循环n*5次才能AC呢？求解释～～ (52) tueiqi123 2011-07-05 10:26:31
  • Re:floyd为何外层循环需要循环n*5次才能AC呢？求解释～～ (33) tueiqi123 2011-07-05 10:28:07