程式碼備份區

題意：

有兩個人要碰面，問說那哪個點碰面可以讓兩個人走的路相加最少，輸出走的長度以及最好的點，如果有多個最好的點就都要輸出

點有A-Z，路有分年輕人可以走以及老人可以走的，然後有單向的路以及雙向的路

解法：

做兩個map，分別是年輕人的路以及老人的路，做 all pair shortest path；要小心有重複的路的話要取值最小的，然後自己到自己是0

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1<<29

int map[2][30][30];
int n;
char str[123];
char a[123],b[123];
int main(){
    int i,j,k;
    int w;
    int c;
    while(scanf("%d",&n)!=EOF &&n ){
        for(i=0;i<26;++i){
            for(j=0;j<26;++j){
                map[0][i][j] = INF;
                map[1][i][j] = INF;
            }
        }
        for(i=0;i<26;++i){
            map[0][i][i] = 0;
            map[1][i][i] = 0;
        }
        while(n--){
            scanf("%s",str);
            w = (str[0]=='Y')?0:1;
            scanf("%s %s %s %d",str,a,b,&c);
            if(map[w][a[0]-'A'][b[0]-'A']>c)
                map[w][a[0]-'A'][b[0]-'A'] = c;
            if(str[0]=='B'  && map[w][b[0]-'A'][a[0]-'A']>c)
                map[w][b[0]-'A'][a[0]-'A'] = c;
        }
        for(w=0;w<2;++w){
            for(k=0;k<26;++k){
                for(i=0;i<26;++i){
                    for(j=0;j<26;++j){
                        if(map[w][i][j] > map[w][i][k]+map[w][k][j])
                            map[w][i][j] = map[w][i][k]+map[w][k][j];
                    }
                }
            }
        }
        scanf("%s %s",a,b);
        j = a[0]-'A';
        k = b[0]-'A';
        for(i=c=0;i<26;++i){
            if(map[0][j][i]+map[1][k][i] < map[0][j][c]+map[1][k][c])
                c = i;
        }
        if(map[0][j][c]+map[1][k][c] >= INF){
            puts("You will never meet.");
        }else {
            printf("%d",map[0][j][c]+map[1][k][c]);
            for(i=c;i<26;++i){
                if(map[0][j][i]+map[1][k][i] == map[0][j][c]+map[1][k][c])
                    printf(" %c",i+'A');
            }
            puts("");
        }
    }

    return 0;
}