首页 > 代码库 > UVA 11280 - Flying to Fredericton(最短路)
UVA 11280 - Flying to Fredericton(最短路)
UVA 11280 - Flying to Fredericton
题目链接
题意:给定一些国家,和两个国家间的花费,现在有一些询问,询问每次最多转k次飞机,最小花费
思路:dijkstra变形,多开一维表示转机次数即可
代码:
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <iostream> #include <string> #include <map> using namespace std; const int MAXNODE = 505; const int MAXEDGE = 5005; typedef int Type; const Type INF = 0x3f3f3f3f; struct Edge { int u, v; Type dist; Edge() {} Edge(int u, int v, Type dist) { this->u = u; this->v = v; this->dist = dist; } }; struct HeapNode { Type d; int ti; int u; HeapNode() {} HeapNode(Type d, int u, int ti) { this->d = d; this->ti = ti; this->u = u; } bool operator < (const HeapNode& c) const { return d > c.d; } }; struct Dijkstra { int n, m; Edge edges[MAXEDGE]; int first[MAXNODE]; int next[MAXEDGE]; bool done[MAXNODE][MAXNODE]; Type d[MAXNODE][MAXNODE]; int p[MAXNODE]; void init(int n) { this->n = n; memset(first, -1, sizeof(first)); m = 0; } void add_Edge(int u, int v, Type dist) { edges[m] = Edge(u, v, dist); next[m] = first[u]; first[u] = m++; } void dijkstra(int s) { priority_queue<HeapNode> Q; for (int i = 0; i < n; i++) for (int j = 0; j <= 100; j++) d[i][j] = INF; d[s][0] = 0; memset(done, false, sizeof(done)); Q.push(HeapNode(0, s, 0)); while (!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; int ti = x.ti; if (done[u][ti]) continue; done[u][ti] = true; for (int i = first[u]; i != -1; i = next[i]) { Edge& e = edges[i]; if (d[e.v][ti + 1] > d[u][ti] + e.dist) { d[e.v][ti + 1] = d[u][ti] + e.dist; Q.push(HeapNode(d[e.v][ti + 1], e.v, ti + 1)); } } } } } gao; int t, n; map<string, int> hash; string name; int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d", &n); gao.init(n); hash.clear(); for (int i = 0; i < n; i++) { cin >> name; hash[name] = i; } int m; scanf("%d", &m); string u, v; int d; while (m--) { cin >> u >> v >> d; gao.add_Edge(hash[u], hash[v], d); } gao.dijkstra(0); printf("Scenario #%d\n", ++cas); int q, num; scanf("%d", &q); while (q--) { scanf("%d", &num); num++; if (num > n - 1) num = n - 1; int ans = INF; for (int i = 0; i <= num; i++) ans = min(ans, gao.d[n - 1][i]); if (ans == INF) printf("No satisfactory flights\n"); else printf("Total cost of flight(s) is $%d\n", ans); } if (t) printf("\n"); } return 0; }
UVA 11280 - Flying to Fredericton(最短路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。