ZOJ 1589 Professor John ~Floyd算法

 這題用Floyd和Dij都可以，但是感覺用Floyd會十分方便，也是第一次使用Floyd算法，一開始沒有這個思路滴，參考別人的。。~~~~（>_<)~~~~

      

 
#include<stdio.h>   
#include<iostream>   
#include<string.h>   
using namespace std;  
int main(void)  
{  
    int ncases,n,i,j,k;  
    int map[30][30],mark[30][30];  
    cin>>ncases;  
    for(int f = 1;f<=ncases;f++)  
    {  
          memset(map,0,sizeof(map));  
          memset(mark,0,sizeof(mark));  
          int flag = 1;   
          cin>>n;  
          char s[4];  
          while(n--)  
          {  
                scanf("%s",s);  
                int a,b;  
                char o;  
                a = s[0]- 'A' + 1;  
                o = s[1];  
                b = s[2]- 'A' + 1;  
                if(o=='<')  
                     map[a][b] = 1;  
                else  
                     map[b][a] = 1;  
          }       
          memcpy(mark,map,sizeof(map));  
          for(k = 1;k<=28;k++)  
              for(i = 1;i<=28;i++)  
                   for(j =1;j<=28;j++)  
                         map[i][j] = map[i][j]||(map[i][k]&&map[k][j]);//這裡很巧妙地將Floyd做了變形。。至少我這個弱菜是這麼認為的，啊哈   
          printf("Case %d:\n",f);  
          for(i = 1;i<=28;i++)  
               for(j =1;j<=28;j++)  
                     if((map[i][j])&&!mark[i][j])  
                      {  
                             printf("%c<%c\n",i+'A'-1,j+'A'-1);  
                             flag = 0;  
                      }  
          if(flag)  
               printf("NONE\n");  
     }  
     return 0;  
 }