Gym 101572 I.Import Spaghetti【Floyd最小环+输出路径】

题目大意：

输出最小环的路径。

思路：

板子= =

Ac代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<map>
#include<stack>
using namespace std;
map<string,int >s;
map<int,string>re;
int n;
int path[605][605];
int mp[605][605];
int dist[605][605];
void add(int u,int v)
{
    mp[u][v]=dist[u][v]=1;
}
void init()
{
    memset(path,0,sizeof(path));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            mp[i][j]=dist[i][j]=0x3f3f3f3f;
        }
    }
}
void getPath(int i ,int j){
    if(i==j) return;
    if(path[i][j]==0) cout<<re[j]<<" ";
    else{
        getPath(i,path[i][j]);
        getPath(path[i][j],j);
    }

}
void Slove()
{

    int x,y,z;
    int minn=0x3f3f3f3f;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(dist[i][j]!=0x3f3f3f3f&&mp[j][k]!=0x3f3f3f3f&&mp[k][i]!=0x3f3f3f3f)
                {
                    if(dist[i][j]+mp[j][k]+mp[k][i]<minn)
                    {
                        x=i,y=j,z=k;
                        minn=dist[i][j]+mp[j][k]+mp[k][i];
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(dist[i][k]!=0x3f3f3f3f&&dist[k][j]!=0x3f3f3f3f)
                {
                    if(dist[i][k]+dist[k][j]<dist[i][j])
                    {
                        dist[i][j]=dist[i][k]+dist[k][j];
                        path[i][j]=k;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(mp[i][i]==1)
        {
            cout<<re[i]<<endl;
            return ;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mp[i][j]==1&&mp[j][i]==1)
            {
                cout<<re[i]<<" "<<re[j]<<" "<<endl;
                return ;
            }
        }
    }
    if(minn==0x3f3f3f3f)printf("SHIP IT\n");
    else
    {
        cout<<re[x]<<" ";
        getPath(x,y);
        cout<<re[z]<<endl;
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            char temp[100000];scanf("%s",temp);
            s[temp]=++cnt;
            re[cnt]=temp;
        }
        for(int i=1;i<=n;i++)
        {
            char temp[100000];scanf("%s",temp);
            char sss[100000];
            int u=s[temp];
            int d;scanf("%d",&d);
            getchar();
            for(int j=0;j<d;j++)
            {
                int l=0;
                int flag=0;
                gets(temp);
                int len=strlen(temp);
                for(int j=0;j<len;j++)
                {
                    if(temp[j]==' ')
                    {
                        flag=1;
                        continue;
                    }
                    if(temp[j]==','||j==len-1)
                    {
                        if(j==len-1)sss[l++]=temp[j];
                        flag=0;
                        sss[l]='\0';
                        int v=s[sss];
                        l=0;
                        add(u,v);
                        continue;
                    }
                    if(flag==1)
                    {
                        sss[l++]=temp[j];
                    }
                }
            }
        }
        Slove();
    }
}