这篇文章继续对最短路问题做相关阐述
主要讲一下负权边的处理
以及状态图建图的技巧和方法

多阶段 Dijkstra

UVALive3561

看一下这个例子的建图过程
LA3561

algorithm\textbf{algorithm}

  • build graph\text{build graph}
    for ∀trip∈[1,NI]\textbf{for} \ \forall \text{trip} \in [1, \text{NI}]
          ~~~~~~get trip List→([toList],len)\text{get trip List} \rightarrow ([\textbf{toList}], len)
          ~~~~~~chooseTicket([toList,len])\text{chooseTicket}([\textbf{toList}, len])

  • chooseTicket(toList,len):\text{chooseTicket}(\textbf{toList}, len):
          ~~~~~~for ∀i∈[0,NT), for ∀k∈[1,tot]\textbf{for} \ \forall i \in [0, \text{NT}), \ \textbf{for} \ \forall k \in [1, tot]
              ~~~~~~~~~~st=(k,tickets[i,0])\textbf{st}=(k,\text{tickets[i,0]})
              ~~~~~~~~~~for ∀j∈[1,tickets(i).size)\textbf{for} \ \forall j \in [1, \text{tickets}(i).\text{size)}
                  ~~~~~~~~~~~~~~if  toList[k]=tickets[i,j],Edge(st,(k+1,tickets[i, j]),cost)\textbf{if} \ \ \textbf{toList}[k]=\text{tickets}[i,j], \textbf{Edge}(\textbf{st}, (k+1, \text{tickets[i, j]}), \text{cost})
                  ~~~~~~~~~~~~~~else Edge(st,(k,tickets[i,j],cost)\textbf{else} \ \textbf{Edge}(\textbf{st}, (k, \text{tickets}[i, j], \text{cost})
                  ~~~~~~~~~~~~~~cost:=(price[ith-Tickets],ticketID)\text{cost}:=(\text{price}[ith\text{-Tickets}], \text{ticketID})

  • run Dijkstra()\text{run } \textbf{Dijkstra}()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

const int maxN = 4000 + 10;
const int inf = 0x3f3f3f3f;
int nCities = 0;
const int maxn = 100;
vector<int> tickets[maxn];
int cost[maxn];
int NT, NI;

// == Graph ==
vector<int> G[maxN];

class Edge {
public:
    int from, to, weight, val;
    Edge() {}
    Edge(int u, int v, int w, int val) : from(u), to(v), weight(w), val(val) {}
};

class Node {
public:
    int u, dist;
    Node() {}
    Node(int u, int dist) : u(u), dist(dist) {}
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
};

vector<Edge> edges;

void initG() {
    _for(i, 0, maxN) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w, int val) {
    edges.push_back(Edge(u, v, w, val));
    G[u].push_back(edges.size() - 1);
}
// == Graph finsihed ==

// == dijkstra ==
int D[maxN], vis[maxN];
int pid[maxN];

void initDij(int st) {
    _for(i, 0, maxN) D[i] = inf;
    D[st] = 0;

    Set(vis, 0);
    Set(pid, 0);
}

void dijsktra(int st) {
    initDij(st);
    priority_queue<Node> que;
    que.push(Node(st, 0));

    while (!que.empty()) {
        int x = que.top().u;
        que.pop();
        if(vis[x]) continue;
        vis[x] = 1;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;
            if(D[y] > D[x] + e.weight) {
                D[y] = D[x] + e.weight;
                pid[y] = G[x][i];
                que.push(Node(y, D[y]));
            }
        }
    }
}

vector<int> getPath(int ed, const int st) {
    vector<int> path;
    while (ed != st) {
        path.push_back(edges[pid[ed]].val);
        ed = edges[pid[ed]].from;
    }
    reverse(path.begin(), path.end());
    return path;
}
// == dijkstra finsihed ==

// == get all tickets ==
map<int, int> cityID;

inline int ID(int x) {
    if(cityID.count(x)) return cityID[x];
    cityID[x] = ++nCities;
    return nCities;
}

inline int ID(int i, int j) {
    return (i - 1) * nCities + j;
}

void getTickets(const int NT) {
    _for(i, 0, NT) {
        tickets[i].clear();
        int len;
        scanf("%d%d", &cost[i], &len);
        while (len--) {
            int x;
            scanf("%d", &x);
            tickets[i].push_back(ID(x));
        }
    }
}
// == get tickets finished ==

// == get trip data ==
vector<int> toList;
int getTrip(const int trip) {
    toList.clear();
    int tot = 0;
    scanf("%d", &tot);

    _for(i, 0, tot) {
        int x;
        scanf("%d", &x);
        toList.push_back(ID(x));
    }

    return tot;
}
// == trip finished ==

// == chooseTicket for trip ==
void chooseTicket(const vector<int>& toList, const int tot) {
    _for(i, 0, NT) _rep(k, 1, tot) {
        int cur = tickets[i][0];
        int k2 = k;

        _for(j, 1, tickets[i].size()) {
            int A = tickets[i][j];
            if(A == toList[k2]) k2++;
            if(k2 > tot) break;

            addEdge(ID(k, cur), ID(k2, A), cost[i], i + 1);
            if(k2 == tot) break;
        }
    }
}
// == chooseTicket finished ==

void init() {
    nCities = 0;
    cityID.clear();
    _for(i, 0, maxn) tickets[i].clear();
    Set(cost, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d", &NT) == 1 && NT) {
        init();

        // get tickets
        getTickets(NT);
        scanf("%d", &NI);
        kase++;

        _rep(trip, 1, NI) {
            int tot = getTrip(trip);
            assert(toList.size() != 0);

            initG();
            chooseTicket(toList, tot);
            int src = ID(1, toList[0]), ed = ID(tot, toList[tot-1]);
            dijsktra(src);

            printf("Case %d, Trip %d: Cost = %d\n", kase, trip, D[ed]);
            printf("  Tickets used:");

            vector<int> res = getPath(ed, src);
            _for(i, 0, res.size()) printf(" %d", res[i]);
            printf("\n");
        }
    }
}

状态建图

UVALive3661
LA3661

algorithm\textbf{algorithm}
build graph\textbf{build} \ \textbf{graph}

  • get vector\text{get vector}

{top, bottom } {left, right }{slash}=(i,j,dir[0,2)) →vector[edges]\begin{gathered} \quad \{\textbf{top,} \ \textbf{bottom} \ \} \ \{\textbf{left,} \ \textbf{right} \ \} \{ \textbf{slash} \} = (i, j, dir[0, 2)) \\ \ \\ \xrightarrow{\text{vector}} \textbf{[edges]} \end{gathered}

  • u=ID(edges)=ID(top(i,j,dir),⋯ )u=\textbf{ID(edges)}=\textbf{ID}(\textbf{top}(i,j,dir), \cdots)
    v=ID(edges)=ID(slash(i,j,dir))v=\textbf{ID}(\textbf{edges}) = \textbf{ID}(\textbf{slash}(i, j, dir))
    add(u,v,cost(slash(i,j,dir)))add(u, v, cost(\textbf{slash}(i, j, dir)))

dijkstra\textbf{dijkstra}

  • st=0, add(0,leftBorder)\textbf{st} = 0, \ add(\textbf{0}, \textbf{leftBorder})
    add(0, bottomBorder)add(\textbf{0,} \ \textbf{bottomBorder})

    ed right=\textbf{ed} \ \textbf{right}=
          ~~~~~~for ∀i∈[0,n)\textbf{for} \ \forall i \in [0, n)
              ~~~~~~~~~~ID(i,m−1,dir=1)\textbf{ID}(i, m-1, dir=1)

    ed top=\textbf{ed} \ \textbf{top}=
          ~~~~~~for ∀i∈[0,m)\textbf{for} \ \forall i \in [0, m)
              ~~~~~~~~~~ID(0,i,dir=0)\textbf{ID}(0, i, dir = 0)

  • run dijkstra()\text{run } dijkstra()
    ans=min⁡(D[ed right], D[ed top])\textbf{ans} = \min (\textbf{D[ed} \ \textbf{right],} \ \textbf{D[ed} \ \textbf{top]})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
const int maxN = 4000000;
int cost[maxn][maxn][3];
int n, m;

// == Graph definition ==
vector<int> G[maxN];
class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int to, int w) : to(to), weight(w) {}
};

class Node {
public:
    int u, dist;
    Node() {}
    Node(int u, int d) : u(u), dist(d) {}
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
};
vector<Edge> edges;

void initG() {
    _for(i, 0, maxN) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == dijkstra ==
int D[maxN], vis[maxN];

void initDij(int st) {
    Set(D, inf);
    D[st] = 0;

    Set(vis, 0);
}

void dijkstra(int st) {
    initDij(st);
    priority_queue<Node> que;
    que.push(Node(st, 0));

    while (!que.empty()) {
        int x = que.top().u;
        que.pop();
        if(vis[x]) continue;
        vis[x] = 1;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;
            if(D[y] > D[x] + e.weight) {
                D[y] = D[x] + e.weight;
                que.push(Node(y, D[y]));
            }
        }
    }
}
// == dijkstra finsihed ==

inline int ID(int i, int j, int dir) {
    return i*m+j+1 + dir*n*m;
}

inline int read() {
    int x;
    scanf("%d", &x);
    return x;
}

// == build graph ==
void getEdge(int *e1, int *e2, int *e3) {
    int *edges[3] = {e1, e2, e3};
    // edges[i]:= (i, j, dir)
    _for(i, 0, 3) _for(j, 0, 3) if(i != j) {
        int u = ID(edges[i][0], edges[i][1], edges[i][2]);
        int v = ID(edges[j][0], edges[j][1], edges[j][2]);
        int w = cost[edges[j][0]][edges[j][1]][edges[j][2]];

        addEdge(u, v, w);
    }
}

void build() {
    _for(i, 0, n - 1) _for(j, 0, m - 1) {
        int top[] = {i, j, 0};
        int bottom[] = {i + 1, j, 0};
        int left[] = {i, j, 1};
        int right[] = {i, j + 1, 1};
        int slash[] = {i, j, 2};

        getEdge(top, right, slash);
        getEdge(bottom, left, slash);
    }

    _for(i, 0, n - 1) {
        int u = ID(i, 0, 1);
        int w = cost[i][0][1];
        addEdge(0, u, w);
    }
    _for(i, 0, m - 1) {
        int u = ID(n - 1, i, 0);
        int w = cost[n - 1][i][0];
        addEdge(0, u, w);
    }
}
// == build finsiehd ==

void init() {
    Set(cost, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d%d", &n, &m) == 2 && n) {
        init();
        initG();

        // get data
        _for(i, 0, n) _for(j, 0, m-1) cost[i][j][0] = read();
        _for(i, 0, n - 1) _for(j, 0, m) cost[i][j][1] = read();
        _for(i, 0, n - 1) _for(j, 0, m - 1) cost[i][j][2] = read();

        // build graph
        build();

        // dijkstra
        dijkstra(0);

        // get ans
        int ans = inf;
        _for(i, 0, n - 1) ans = min(ans, D[ID(i, m - 1, 1)]);
        _for(i, 0, m - 1) ans = min(ans, D[ID(0, i, 0)]);

        //debug(ans);

        printf("Case %d: Minimum = %d\n", ++kase, ans);
    }
}

最短路和dp

ZOJ1232

  • run floyd()\textbf{run} \ floyd()
    f(i,j)←f(i,k)+f(k,j)f(i,j) \leftarrow f(i, k) + f(k, j)
          ~~~~~~if k∈[1,A],D[i,j]⩽L\textbf{if} \ k \in [1,A], D[i,j] \leqslant L
              ~~~~~~~~~~(st→k) can use magic boot, valid(i,j)=1(\text{st} \rightarrow k) \text{ can use magic boot}, \ \textbf{valid}(i, j) = 1

  • dp equation\textbf{dp} \ \textbf{equation}

dp(i,k)=min⁡{∀j<i,dp(j,k−1)valid(i,1)=1∀j<i,dp(j,k)+D(j→i)\begin{gathered} dp(i,k)=\min\left\{\begin{gathered} \forall j<i, & d p(j, k-1) && \text {valid}(i, 1)=1 \\ \forall {j<i}, & d p(j, k)+D(j\rightarrow i) \end{gathered}\right. \end{gathered}

  • dp algorithm\text{dp algorithm}
    st:=\textbf{st:=}
          ~~~~~~for ∀i∈V,dp(i,0)=D(st,i)\textbf{for} \ \forall i \in V, dp(i, 0) = D(st, i)
          ~~~~~~for ∀k∈[0,K],dp(st,k)=0\textbf{for} \ \forall k \in [0, K], dp(st, k) = 0
    ed:=\textbf{ed:=}
          ~~~~~~dp(ed,K)\text{dp}(ed, K)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;
int D[maxn][maxn];
int valid[maxn][maxn];
int a, b, m, L, K;

void init() {
    Set(D, inf);
    _for(i, 0, maxn) D[i][i] = 0;

    Set(valid, 0);
}

void build() {
    _for(i, 0, m) {
        int u, v, L;
        scanf("%d%d%d", &u, &v, &L);
        D[u][v] = D[v][u] = min(D[v][u], L);
    }
}

void floyd() {
    _rep(k, 1, a+b) _rep(i, 1, a+b) _rep(j, 1, a+b) {
        if(D[i][j] > D[i][k] + D[k][j]) {
            D[i][j] = D[i][k] + D[k][j];
        }
        if(k <= a && D[i][j] <= L) valid[i][j] = 1;
    }
}

// == dp ==
const int st = 1;
int dp[maxn][maxn];

void initDP() {
    Set(dp, inf);
    _rep(i, 1, a+b) dp[i][0] = D[st][i];
    _rep(k, 0, K) dp[st][k] = 0;
}

void solve() {
    _rep(i, 1, a+b) _rep(k, 1, K) {
        _for(j, 1, i) {
            if(valid[i][j] == 1)
                dp[i][k] = min(dp[i][k], dp[j][k - 1]);
            dp[i][k] = min(dp[i][k], dp[j][k] + D[j][i]);
        }
    }
}
// == dp finished ==

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    scanf("%d", &kase);

    while (kase--) {
        init();
        scanf("%d%d%d%d%d", &a, &b, &m, &L, &K);

        // build
        build();

        // floyd
        floyd();

        // dp
        initDP();
        solve();

        printf("%d\n", dp[a+b][K]);
    }
}

最短路和dp（二）

这里的状态转移比较特殊
在每一个节点 uu, 加油，必须一升一升加

state(u,gas,cost)\textbf{state}(u, gas, cost)

x(u,gas,cost)→{x(u,gas+1,cost+p(u))gas+1⩽cx((u→v),gas−w(u,v),cost)gas−w(u,v)⩾0x(u, g a s, cost) \rightarrow\left\{\begin{gathered} x(u, g a s+1, cost+p(u)) && g a s+1 \leqslant c \\ x((u \rightarrow v), g a s-w(u, v), cost) && g a s-w(u, v) \geqslant 0 \end{gathered}\right.

algorithm\textbf{algorithm}
run dijkstra()\text{run } dijkstra()
      ~~~~~~vis(u,gas)=1 , mark node complete\textbf{vis}(u, gas) = 1\text{ , mark node complete}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
int n, m;
int P[maxn];

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int from, to, weight;
    Edge() {}
    Edge(int u, int v, int w) : from(u), to(v), weight(w) {}
};

vector<Edge> edges;

void initG() {
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(u, v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == Dijkstra ==
class State {
public:
    int u, gas, cost;
    bool operator< (const State& rhs) const {
        return cost > rhs.cost;
    }

    State() {}
    State(int u, int g, int c) : u(u), gas(g), cost(c) {}
};

int vis[maxn][maxn];
int ans = inf;

void initDij(int st, const int C) {
    Set(vis, 0);
    ans = inf;
}

bool dijkstra(int st, int ed, const int C) {
    initDij(st, C);
    priority_queue<State> que;
    que.push(State(st, 0, 0));

    while (!que.empty()) {
        State x = que.top();
        que.pop();

        if(x.u == ed) {
            ans = x.cost;
            return true;
        }

        if(vis[x.u][x.gas]) continue;
        vis[x.u][x.gas] = 1;

        if(x.gas + 1 <= C) {
            State nxt(x.u, x.gas + 1, x.cost + P[x.u]);
            que.push(nxt);
        }
        _for(i, 0, G[x.u].size()) {
            const Edge& e = edges[G[x.u][i]];
            int y = e.to;

            if(x.gas >= e.weight) {
                State nxt(y, x.gas - e.weight, x.cost);
                que.push(nxt);
            }
        }
    }
    return false;
}
// == Dijkstra finsihed ==

void init() {
    Set(P, 0);
}

void solve() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int st, ed, C;
        scanf("%d%d%d", &C, &st, &ed);
        if(dijkstra(st, ed, C)) printf("%d\n", ans);
        else printf("impossible\n");
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    initG();
    init();
    // get data
    _for(i, 0, n) scanf("%d", &P[i]);
    _for(i, 0, m) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    // each query, dijkstra
    solve();
}

最短路拓展

UVA11280

algorithm: Dijkstra(st)\textbf{algorithm:} \ \text{Dijkstra}(st)

state(u,k)k denotes number of stays\textbf{state}(u, k) \quad \text{k denotes } \textbf{number} \ \textbf{of} \ \textbf{stays}

for ∀e(x,y)\textbf{for} \ \forall e(x, y)
      ~~~~~~D(y,k+1)←D(x,k)+w(x,y)D(y, k+1) \leftarrow D(x, k) + w(x, y)

st→ed, query(S)st\rightarrow ed, \text{ query}(S)
start:=(st,0)\textbf{start:=} (st, 0)
end:= for ∀k∈[1,S]\textbf{end:=} \ \textbf{for} \ \forall k \in [1, S]
          ~~~~~~~~~~ans = min⁡(D(ed,k))\textbf{ans} \ \textbf{=} \ \min(D(ed, k))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int tot = 0;
map<string, int> id;
int n, m;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int from, to, weight;
    Edge() {}
    Edge(int u, int v, int w) : from(u), to(v), weight(w) {}
};

vector<Edge> edges;

void initG() {
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(u, v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == Dijkstra ==
class State {
public:
    int u, k, dist;
    State() {}
    State(int u, int k, int dist) : u(u), k(k), dist(dist) {}

    bool operator< (const State& rhs) const {
        return dist > rhs.dist;
    }
};


int vis[maxn][maxn];
int D[maxn][maxn];

void initDij(const int st) {
    Set(vis, 0);
    Set(D, inf);
    D[st][0] = 0;
}

void dijkstra(const int st) {
    initDij(st);
    priority_queue<State> que;
    que.push(State(st, 0, 0));

    while (!que.empty()) {
        State x = que.top();
        que.pop();
        if(vis[x.u][x.k]) continue;
        vis[x.u][x.k] = 1;

        _for(i, 0, G[x.u].size()) {
            const Edge& e = edges[G[x.u][i]];
            int y = e.to;

            if(D[y][x.k+1] > D[x.u][x.k] + e.weight) {
                D[y][x.k+1] = D[x.u][x.k] + e.weight;
                que.push(State(y, x.k+1, D[y][x.k+1]));
            }
        }
    }
}
// == Dijkstra finished ==

inline void getID(const string& str) {
    if(id.count(str)) return;
    else {
        id[str] = ++tot;
        return;
    }
}

void solve() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int S;
        scanf("%d", &S);

        int ans = inf;
        _rep(k, 1, S + 1) ans = min(ans, D[n][k]);

        //debug(ans);
        if(ans != inf) printf("Total cost of flight(s) is $%d\n", ans);
        else printf("No satisfactory flights\n");
    }
}

void init() {
    tot = 0;
    id.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);

    _rep(kase, 1, T) {
        printf("Scenario #%d\n", kase);
        init();
        initG();

        // get city data
        scanf("%d", &n);
        _for(i, 0, n) {
            string str;
            cin >> str;
            getID(str);
        }
        // get flights data
        scanf("%d", &m);
        _for(i, 0, m) {
            string from, to;
            int w;
            cin >> from >> to >> w;
            int u = id[from], v = id[to];
            //debug(u), debug(v), debug(w), puts("");

            addEdge(u, v, w);
        }
        // get query
        dijkstra(1);
        solve();
        if(kase != T) cout << endl;
    }
}