UVA - 11280 Flying to Fredericton——spfa

UVA - 11280 Flying to Fredericton——spfa

用二维的dis【i】【j】表示遍历到点i且经过的点数为j时的最短路，求解经过点数不超过x的最短路时遍历dis【n】【1—x+2】就可以了

#include #include #include #include #include #include #include #include

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

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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。