Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这个题目为什么FLOYD也过不了啊?快哭了，谢谢各位大牛帮忙看看！！！

Posted by wangfengbo at 2008-05-24 11:02:35 on Problem 1122
```Source Code

Problem: 1122  User: wangfengbo
Memory: N/A  Time: N/A

Source Code
#include <iostream>
#include <sstream>
#include <cstdlib>

using namespace std;

struct tt
{
int begin,time;
}start[21];

int map[21][21];
int path[21][21]={0};
int cmp(const void *a,const void *b)
{
tt *c,*d;
c = (tt*)a;
d = (tt*)b;
return c->time - d->time;
}

void pathprint(int index,int dest)
{
int temp;
if(index == dest)
{
printf("%d",index);
return ;
}
if(dest == 0)
printf("%d\t",index);
else
{
if(index == 0)
printf("%d\t",dest);
else
{
temp = path[index][dest];
if(temp == 0)
printf("%d\t%d\t",index,dest);
else
{
pathprint(index,path[index][temp]);
printf("%d\t",temp);
pathprint(path[index][temp],dest);
}
}
}
}

int main()
{
stringstream ss;
int i,j,k,n,des,fire,temp;
char s[100],ch;
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j] == -1)
map[i][j] = 1000000;
}
}
while(ch=getchar(),ch!='\n');
gets(s);
ss<<s;
ss>>des;
i=0;
while(ss>>temp)
start[i++].begin=temp;
fire = i;
//floyd
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][j] > (temp = map[i][k]+map[k][j]))
{
map[i][j] = temp;
path[i][j]=k;
}
}
}
}

for(i=0;i<fire;i++)
start[i].time = map[start[i].begin][des];
qsort(start,fire,sizeof(start[0]),cmp);
printf("Org\tDest\tTime\tPath\n");
for(i=0;i<fire;i++)
{
printf("%d\t%d\t%d\t",start[i].begin,des,start[i].time);
pathprint(start[i].begin,des);
printf("\n");
}
printf("\n");
return 0;
}

```

Followed by: