UVA - 11280 Flying to Fredericton——spfa

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> P;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
int T, n, m, q;
string s;
map<string, int> id;
vector<P> G[maxn];
int dis[maxn][maxn];
bool vis[maxn][maxn];
void init() {
    id.clear();
    for (int i = 1; i <= n; i++) G[i].clear();
}
void spfa(int s) {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s][1] = 0;
    vis[s][1] = true;
    queue<P> q;
    q.push(make_pair(s, 1));
    while (!q.empty()) {
        P p = q.front(); q.pop();
        int u = p.first, cnt = p.second;
        vis[u][cnt] = false;
        for (unsigned int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].first, cost = G[u][i].second;
            if (dis[v][cnt+1] > dis[u][cnt] + cost) {
                dis[v][cnt+1] = dis[u][cnt] + cost;
                if (!vis[v][cnt+1]) {
                    vis[v][cnt+1] = true;
                    q.push(make_pair(v, cnt+1));
                }
            }
        }
    }
}
int main() {
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++) {
            cin >> s;
            id[s] = i;
        }
        scanf("%d", &m);
        int u, v, cost;
        for (int i = 1; i <= m; i++) {
            cin >> s;
            u = id[s];
            cin >> s;
            v = id[s];
            scanf("%d", &cost);
            if (u > v) swap(u, v);
            G[u].push_back(make_pair(v, cost));
        }
        spfa(1);
        scanf("%d", &q);
        int x;
        if (kase != 1) printf("\n");
        printf("Scenario #%d\n", kase);
        for (int i = 1; i <= q; i++) {
            scanf("%d", &x);
            x = min(x, n);
            int ans = INF;
            for (int j = 1; j <= x + 2; j++) {
                ans = min(ans, dis[n][j]);
            }
            if (ans == INF) printf("No satisfactory flights\n");
            else printf("Total cost of flight(s) is $%d\n", ans);
        }
    }
    return 0;
}