#include <stdio.h>
#define INF 1000000000
int i, j, u, vv, w_u_vv, V, n, w, Q, counter, s, t;
int dist[1000];
int AdjList[1000][1000];
int weight[1000][1000];
int sz[1000];
int change;
int main() {
 scanf("%d", &V);
 for (i = 0; i < V; i++) { scanf("%d", &n); sz[i] = 0; while (n--) { scanf("%d %d", &j, &w); AdjList[i][sz[i]] = j; weight[i][sz[i]] = w; sz[i]++; } } counter = 0; scanf("%d", &Q); while (Q--) { scanf("%d %d", &s, &t); for (i = 0; i < V; i++) dist[i] = INF; dist[s] = 0; for (i = 0; i < V-1; i++) { change = 0; for (u = 0; u < V; u++) for (j = 0; j < sz[u]; j++) { counter++; if (counter> 1000000) {
 printf("TLE because iteration counter> 1000000\n");
 return 1;
 }
 vv = AdjList[u][j];
 w_u_vv = weight[u][j];
 if (dist[u] + w_u_vv < dist[vv]) {
 dist[vv] = dist[u] + w_u_vv;
 change = 1;
 }
 }
 if (!change) // the optimized BellmanFord
 break;
 }
 printf("%d\n", dist[t]);
 }
 printf("The value of counter is: %d\n", counter);
 return 0;
}
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="https://www.acmicpc.net/data/source/OptimizedBellmanFord.c">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://www.acmicpc.net/data/source/OptimizedBellmanFord.c" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>