Uva 383 Shipping Routes ( BFS )

이 문제는 가장 짧은 경로를 구하는데, 각 경로의 권한이 같기 때문에 BFS는 충분하다
다만 출력은 주의해야 한다. 비교적 복잡하다. 빈칸은 공행, 특히 DATA 뒤의 대호는 두 개의 빈칸이 있어야 한다.
코드:

#include <cstdio>
#include <string>
#include <iostream>
#include <map>
#include <cstring>
#include <queue>
using namespace std;

const int N = 35;
const int INF = 1000000;
int n, m, p;
int T, icase;
int g[N][N], d[N];
int siz;
map <string, int> mp;
int bfs( int s, int t, int c ) {
    for ( int i = 1; i <= n; ++i ) d[i] = INF;
    queue <int> q;
    bool vis[N];
    memset(vis, 0, sizeof(vis));
    vis[s] = true; q.push(s);
    d[s] = 0;
    while ( !q.empty() ) {
        int u = q.front(); q.pop(); 
        for ( int i = 1; i <= n; ++i ) {
            if ( g[u][i] && d[i] > d[u] + 1 ) {
                d[i] = d[u] + 1;
                //vis[i] = true;
                q.push(i);
            }
        }
    }
    if ( d[t] < INF ) return d[t] * c * 100;
    return INF;
}


int main() 
{
    icase = 1;
    scanf("%d", &T);
    while ( T-- ) {
        mp.clear();
        memset(g, 0, sizeof(g));
        scanf("%d%d%d", &n, &m, &p);
        getchar();
        for ( int i = 1; i <= n; ++i ) {
            string s;  cin >> s; mp[s] = i;
        }
        for ( int i = 1; i <= m; ++i ) {
            string s, t;
            int u, v;
            cin >> s >> t;
            u = mp[s], v = mp[t];
            g[u][v] = g[v][u] = 1;
        }
        if( icase == 1 ) printf("SHIPPING ROUTES OUTPUT

");
        printf("DATA SET  %d

", icase++);
        for ( int i = 0; i < p; ++i ) {
            int w;
            string s1, s2;
            cin >> w >> s1 >> s2;
            int u = mp[s1], v = mp[s2];
            int ans = bfs( u, v, w );
            if( d[v] == INF ) printf("NO SHIPMENT POSSIBLE
");
            else printf("$%d
", ans);
        }
        printf("
");
        if ( T == 0 ) printf("END OF OUTPUT
");
    }
}