int Map[120][120],N,Maxn=9999999；
int Path[120][120],Dep=0；
bool Bo[120]；
void Cout(int k){
Path[++Dep][1]=k；
Path[Dep][0]=1；
Bo[k]=false；
for (int i=k+1；i<=N；i++)
if (Map[k][i]!=Maxn && Map[k][i]!=0){
Path[Dep][++Path[Dep][0]]=i；
Bo[i]=false；
}
}
int main()
{
scanf("%d",&N)；
for (int i=1；i<=N；i++){
for (int j=1；j<=N；j++){
scanf("%d",&Map[i][j])；
if (!Map[i][j]) Map[i][j]=Maxn；
}
Bo[i]=true；
}
for (int k=1；k<=N；k++)
for (int i=1；i<=N；i++) if (i!=k)
for (int j=1；j<=N；j++) if (i!=j && k!=j)
if (Map[i][k]+Map[k][j]<Map[i][j])
Map[i][j]=Map[i][k]+Map[k][j]；
for (int i=1；i<=N；i++)
if (Bo[i])
Cout(i)；
printf("%d\n",Dep)；
for (int i=1；i<=Dep；i++){
for (int j=1；j<Path[i][0]；j++)
printf("%d ",Path[i][j])；
printf("%d \n",Path[i][Path[i][0]])；
}
return 0；
}
用了2种算法也A不了，我不行了 RP全爆
1种超时 另1种80~~~~
#include<stdio.h>
int Map[520][520],Path[520][520],Search[520],
N,Ans=0,Maxn=9999999；
bool Bo[520],bo[520]；
void work(int k){
Ans++；Path[Ans][0]=1；Path[Ans][1]=k；
for (int i=1；i<=N；i++) {
Search[i]=Map[k][i]；
bo[i]=true；
}
Search[k]=0；bo[k]=false；
int minn ,p；
for (int i=1；i<N；i++){
minn=Maxn；
for (int j=1；j<=N；j++)
if (bo[j] && Search[j]<minn){
minn=Search[j]；
p=j；
}
bo[p]=false；
for (int j=1；j<=N；j++)
if (bo[j] && Search[j]>Search[p]+Map[p][j])
Search[j]=Search[p]+Map[p][j]；
}
for (int i=k+1；i<=N；i++)
if (Search[i]!=Maxn && Search[i]!=0){
Path[Ans][++Path[Ans][0]]=i；
Bo[i]=false；
}
}
int main()
{
scanf("%d",&N)；
for (int i=1；i<=N；i++){
for (int j=1；j<=N；j++){
scanf("%d",&Map[i][j])；
if (Map[i][j]==0) Map[i][j]=Maxn；
}
Bo[i]=true；
}
for (int i=1；i<=N；i++)
if (Bo[i])
work(i)；
printf("%d\n",Ans)；
for (int i=1；i<=Ans；i++){
for (int j=1；j<=Path[i][0]；j++)
printf("%d ",Path[i][j])；
printf("\n")；
}
return 0；
}