1837. Isenbaev's Number(floyd)

1837

被数据结构部分打击的不行了 换地 刷点简单的 图论第一题 floyd水过

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<string>

 #include<map>

 using namespace std;

 int w[][];

 #define INF 0xfffffff

 map<string,int>f;

 struct node

 {

     char s[];

     int id;

 }p[];

 bool cmp(node a,node b)

 {

     return strcmp(a.s,b.s)<;

 }

 int main()

 {

     int i,j,n,k,g=,u=;

     char s1[],s2[],s3[];

     for(i =  ; i <=  ; i++)

         for(j =  ; j <=  ; j++)

         w[i][j] = INF;

     scanf("%d",&n);

     for(i = ; i <= n ; i++)

     {

         scanf("%s%s%s",s1,s2,s3);

         if(!f[s1])

         {

             g++;

             f[s1] = g;

             p[g].id = g;

             if(strcmp(s1,"Isenbaev")==)

             u = g;

             strcpy(p[g].s,s1);

         }

         if(!f[s2])

         {

             g++;

             f[s2] = g;

             p[g].id = g;

             if(strcmp(s2,"Isenbaev")==)

             u = g;

             strcpy(p[g].s,s2);

         }

         if(!f[s3])

         {

             g++;

             f[s3] = g;

             p[g].id = g;

             if(strcmp(s3,"Isenbaev")==)

             u = g;

             strcpy(p[g].s,s3);

         }

         w[f[s1]][f[s2]] = ;

         w[f[s2]][f[s1]] = ;

         w[f[s1]][f[s3]] = ;

         w[f[s3]][f[s1]] = ;

         w[f[s2]][f[s3]] = ;

         w[f[s3]][f[s2]] = ;

     }

     for(i = ; i <= g ; i++)

     w[i][i] = ;

     for(i = ;i <= g ; i++)

         for(j = ; j <= g ; j++)

             for(k = ; k <= g ; k++)

             if(w[j][k]>w[j][i]+w[i][k])

             w[j][k] = w[j][i]+w[i][k];

     sort(p+,p+g+,cmp);

     for(i = ; i <= g ; i++)

     {

         if(u&&w[p[i].id][u]!=INF)

         printf("%s %d\n",p[i].s,w[p[i].id][u]);

         else

         printf("%s undefined\n",p[i].s);

     }

     return ;

 }