题意：有向图最小环，输出方案。
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
int n;
map<string,int>ma;
string mb[505];
int a[505][505],ans=2147483647;
int path[505][505];
int main(){
//freopen("i.in","r",stdin);
memset(a,0x7f,sizeof(a));
scanf("%d",&n);
for(int i=1;i<=n;++i){
cin>>mb[i];
ma[mb[i]]=i;
}
string x,z;
int y;
for(int i=1;i<=n;++i){
cin>>x>>y;
if(!y){
continue;
}
int ma_x=ma[x];
int cnt=0;
while(1){
cin>>z;
if(z=="import"){
continue;
}
if(z[z.length()-1]!=','){
++cnt;
}
else{
z.erase(z.length()-1,1);
}
if(ma[z]==ma_x){
cout<<z<<endl;
return 0;
}
a[ma_x][ma[z]]=1;
path[ma_x][ma[z]]=ma[z];
if(cnt==y){
break;
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
for(int k=1;k<=n;++k){
if(i!=j && j!=k && a[j][i]<2000000000 && a[i][k]<2000000000){
if(a[j][i]+a[i][k]<a[j][k]){
a[j][k]=a[j][i]+a[i][k];
path[j][k]=path[j][i];
}
else if(a[j][i]+a[i][k]==a[j][k]){
if(path[j][k]==0){
path[j][k]=path[j][i];
}
}
}
}
}
}
int I,J;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(i!=j){
if(ans-a[i][j]>a[j][i]){
ans=a[i][j]+a[j][i];
I=i;
J=j;
}
}
}
}
if(ans>2000000000){
puts("SHIP IT");
return 0;
}
int U=I;
cout<<mb[U];
while(U!=J){
cout<<' '<<mb[path[U][J]];
U=path[U][J];
}
U=J;
while(path[U][I]!=I){
cout<<' '<<mb[path[U][I]];
U=path[U][I];
}
puts("");
return 0;
}
附无向图最小环（转自 http://www.cnblogs.com/kane0526/archive/2012/11/09/2763170.html）：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; const int maxn=110;
const int INF=0x7ffffff;
int dist[maxn][maxn], map[maxn][maxn];
int pre[maxn][maxn];
int path[maxn];
int n, m, num, minc; void floyd()
{
minc=INF;
for(int k=1; k<=n; k++)
{
for(int i=1; i<k; i++)
for(int j=i+1; j<k; j++)
{
int ans=dist[i][j]+map[i][k]+map[k][j];
if(ans<minc) //找到最优解
{
minc=ans;
num=0;
int p=j;
while(p!=i) //逆向寻找前驱遍历的路径并将其存储起来
{
path[num++]=p;
p=pre[i][p];
}
path[num++]=i;
path[num++]=k;
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
pre[i][j]=pre[k][j];
}
}
}
} int main()
{
int u, v, cost;
while(cin >> n)
{
if(n<0) break;
cin >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
dist[i][j]=map[i][j]=INF;
pre[i][j]=i;
}
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&u,&v,&cost);
if(dist[u][v]>cost) //处理重边
map[u][v]=map[v][u]=dist[u][v]=dist[v][u]=cost;
}
floyd();
if(minc==INF)
printf("No solution.\n");
else
{
printf("%d",path[0]);
for(int i=1; i<num; i++)
printf(" %d",path[i]);
puts("");
}
}
return 0;
}