floyed n^3的

也可以n^2*m的删边dijkstra

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：231ms

居然。。。。。

日,1个eof 搞了半天,还有,读入要用readln...

算法:FLOYD修改(具体参考 为什么封我号？ 的程序)

我写seekeof 0分

eof 100分...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：225ms

速度怎么这么慢，怎么优化的？

原本不对的，只是写错了一个变量。

以整个下午。我的青春啊。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

FLOYED 的改进型就是强啊 感谢大牛的思路

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

FLOYD这么快？

我用m次 dijstra +下面魂牛所说的优化...超了4个数据-_-b...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 41ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：169ms

O(N^3)的算法也这么快??

思路:FLOYD改进型.

标准的改进Floyd求最小环嘛 dijkstra多麻烦

30行code解决

用最短路树理论上应该更优,但不知为什么这题用最短路树反而会慢??

最短路树时间复杂度=N*(N*N+M) MAX

那个什么，seekeof导致我第二个点错误。

eof几乎就没对的。

最后，只好在第二的点上写：

for i:=1 to 10 do writeln('No solution.');halt;

就过了

千万不能用SeekEoF！！！

我用SeekEoF错误一大堆，Eof一下子就全过了。

216是什么错误啊?

SPOJ239("BTOUR").

那道题数据范围大一些。

呃。谁能告诉我第2个点格式错误是什么意思

m次dijkstra即可

每次找一条边，把这条边封上，然后用dijkstra求一下这条边两个端点间的最短路

加一个优化：如果某条边的长度不小于当前最优解，则这条边就不必理它了

n^4居然都过了……

用dijkstra貌似会超时 floyd才是王道哈

//求大神指导下这段代码哪里错了
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int main()
{
int n,m,i,j,k,dis[110][110];
while(cin>>n>>m)
{
int Min=INT_MAX;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=INT_MAX;
for(i=1;i<=m;i++)
{
int temp1,temp2;
cin>>temp1>>temp2;
cin>>dis[temp1][temp2];
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j&&dis[k][j]<INT_MAX&&dis[i][k]<INT_MAX)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(dis[i][j]<INT_MAX&&dis[j][i]<INT_MAX)
dis[i][j]+=dis[j][i];
else
dis[i][j]=INT_MAX;
}
Min=min(Min,*min_element(dis[i]+1,dis[i]+1+n));
}
if(Min<INT_MAX)
cout<<Min<<endl;
else
cout<<"No solution."<<endl;
}
}