【求助】请问NOIP2012普及组第4题“文化之旅”为何不能用Floyd？_noip吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：15,149贴子：
【求助】请问NOIP2012普及组第4题“文化之旅”为何不能用Floyd？收藏
我认为Floyd可以枚举路径上的每两个点，所以应该可以在进行Floyd时判断是否互相排斥。神牛说是由于数据太弱导致Floyd能够AC。所以想问问为什么Floyd在这题是错误算法？
附问题描述：有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家） 。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家） 。 现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。
因为存在后效性，你不知道从i到k再到j时你不知道i到k经过了哪些文化而k到j又是哪些。。
因为不满足无后效性，所以不可以使用Floyd算法。比如说，你从1可以到2，那么你从2到1呢？要看你之前有没有经过1，所以就没有无后效性了。
#include&stdio.h&#define INF 0x3fffffff#define min(a,b) ((a)&(b)? (a):(b))int def[200][200], f[200][200], rch[200][200];int c[200];int main(void){
freopen(&culture.in&,&r&,stdin);
freopen(&culture.out&,&w&,stdout);
int i, j, k, n, e, t1, t2, t3, cul, sta,
scanf(&%d%d%d%d%d&, &n, &cul, &e, &sta, &end);
for (i=1;i&=n;i++) scanf(&%d&, &c[i]);
for (i=1;i&=i++)
for (j=1;j&=j++)
scanf(&%d&, &def[i][j]);
def[i][i]=1;
for (i=1;i&=n;i++)
for (j=1;j&=n;j++)
if (!def[c[i]][c[j]]) rch[j][i]=1;
for (i=1;i&=n;i++)
for (j=1;j&=n;j++)
f[i][j]=INF;
for (i=1;i&=e;i++)
scanf(&%d%d%d&, &t1, &t2, &t3);
if (rch[t1][t2]) f[t1][t2]=min(f[t1][t2], t3);
if (rch[t2][t1]) f[t2][t1]=min(f[t2][t1], t3);
for (k=1;k&=n;k++)
for (i=1;i&=n;i++)
for (j=1;j&=n;j++)
if (i!=j && i!=k && j!=k)
if (rch[i][k] && rch[k][j] && rch[i][j])
f[i][j]=min(f[i][j], f[i][k]+ f[k][j]);
if (f[sta][end]==INF) printf(&-1\n&);
else printf(&%d\n&, f[sta][end]);
fclose(stdin);
fclose(stdout);
return 0;}
输入输出格式：
【输入】 输入文件culture.in。 第一行为五个整数N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为1到N），文化种数（文化编号为1到 K），道路的条数，以及起点和终点的编号（保证S 不等于T）； 第二行为 N 个整数，每两个整数之间用一个空格隔开，其中第 i 个数 Ci，表示国家 i的文化为Ci。 接下来的K行，每行 K个整数，每两个整数之间用一个空格隔开，记第 i行的第j个数为aij，aij= 1 表示文化 i排斥外来文化j（i等于j时表示排斥相同文化的外来人），aij= 0表示不排斥（注意i排斥j并不保证j一定也排斥i）。 接下来的M行，每行三个整数 u，v，d，每两个整数之间用一个空格隔开，表示国家u与国家v有一条距离为 d的可双向通行的道路（保证 u 不等于v，两个国家之间可能有多条道路）。
输出文件名为culture.out。 输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1）。
4 4 4 1 41 2 3 40 0 0 00 0 0 10 0 0 00 1 0 01 2 12 3 11 3 103 4 1
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或C++一道选择题...求助 第四题为什么选B？C++一道选择题...求助第四题为什么选B？_百度作业帮
C++一道选择题...求助 第四题为什么选B？C++一道选择题...求助第四题为什么选B？
C++一道选择题...求助 第四题为什么选B？C++一道选择题...求助第四题为什么选B？
会因为出现二义性。第三个Add同样可以值接受两个double实参，他的第三个形参有默认值。至于你选择的A，int是可以向double转换的。但如果是B的话编译器就不知道调用哪个了。double Add(double a,double b); double Add(double a,double b,double c = 0);都可以，就会出现二义性。会报错。
貌似数据类型的问题}