如何评价网站是否做的好,做网站作品是静态,seo搜索引擎优化入门,.mil域名的网站UVA1048/LA3561 Low Cost Air Travel 题目链接题意输入格式输出格式 分析AC 代码 题目链接 本题是2006年ICPC世界总决赛的A题
题意 很多航空公司都会出售一种联票#xff0c;要求从头坐#xff0c;上飞机时上缴机票#xff0c;可以在中途任何一站下飞机。比如#xff0c;假… UVA1048/LA3561 Low Cost Air Travel 题目链接题意输入格式输出格式 分析AC 代码 题目链接 本题是2006年ICPC世界总决赛的A题
题意 很多航空公司都会出售一种联票要求从头坐上飞机时上缴机票可以在中途任何一站下飞机。比如假设你有一张“城市1-城市2-城市3”的联票你不能用来只从城市2飞到城市3因为必须从头坐也不能先从城市1飞到城市2再用其他票飞到其他城市玩回到城市2后再用原来的机票飞到城市3因为机票已经上缴。 这里有一个例子。假设有3种票每种票的情况如下所示 ∙ \bullet ∙ 票1城市1-城市3-城市4票价225美元 ∙ \bullet ∙ 票2城市1-城市2票价200美元 ∙ \bullet ∙ 票3城市2-城市3票价50美元 你想从城市1飞到城市3有两种方法可以选择。买票1只飞第一段买票2和3通过城市2中转。显然第一种方法比较省钱虽然浪费了一段。 给出票的信息以及一个或多个行程单你的任务是买尽量少的票同一种票可以买多张使得总花费最小。输入保证行程总是可行的。行程单上的城市必须按顺序到达但中间可以经过一些辅助城市。
输入格式 输入包含多组数据。每组数据第一行为一个整数NT即联票的种类数。以下NT行每行为一个联票描述其中第一个整数为票的价格然后是联票上城市的数目以及这些城市的整数编号按顺序给出。接下来为一个整数NI即需要计算最小花费的行程单数目。以下NI行每行为一个行程单其中一个整数为行程单上的城市数目包括起始城市以及这些城市的编号按顺序给出每个城市编号可取任意整数但唯一。输入保证每组数据最多包含20种联票和20个行程单每张票或者行程单上有至少2个最多10个城市。票价不超过$10000。联票或者行程单上的相邻城市保证不同。票和行程单都从1开始编号。输入结束标志为NT0。
输出格式 对于每组数据的每张行程单输出最小花费和对应的方案按顺序详见样例输出。输出保证唯一。
分析 题目交代每个城市的编号是任意整数但唯一因此需要对城市重新编号不同城市最多200个。行程单上的城市必须按顺序到达但中间可以经过一些辅助城市这里其实隐含了一点只能从行程单的首个城市作为初始出发点。 充分理解题意之后可以知道本题其实是单源最短路问题可以用spfa处理只不过需要重新定义状态点d[i][j]表是当前旅行到了城市i已经走完行程单前j个城市的最小花费。 可以用结构体struct {int v, k, t;} ans[N][M]记录最短路径ans[i][j]记录当前旅行到了城市i已经走完行程单前j个城市花费最小时上个行程旅行到了城市v已经走完行程单前k个城市对应转机的机票t。
AC 代码
#include iostream
#include cstring
#include queue
using namespace std;#define T 21
#define M 11
#define N 202
int d[N][M], f[N][M], a[T][M], w[T], c[T], b[M], id[N], m, n, t, x, kase 0;
struct node {int v, k;} p; struct {int v, k, i;} ans[N][M];int find(int v) {for (int i0; ix; i) if (id[i] v) return i;id[x] v;return x;
}int bfs() {cin m;for (int i0, v; im; i) cin v, b[i] find(v);memset(d, 1, sizeof(d)); memset(f, 0, sizeof(f)); queuenode q;for (int i1; it; i) if (a[i][0] b[0]) for (int j1, k1, v; jc[i] km; j) {if ((v a[i][j]) b[k]) k;if (w[i] d[v][k]) {d[v][k] w[i]; ans[v][k] {0, 0, i};if (km !f[v][k]) q.push({v, k}), f[v][k] 1;}}while (!q.empty()) {p q.front(); q.pop();int v0 p.v, k0 p.k, g d[v0][k0]; f[v0][k0] 0;for (int i1; it; i) if (a[i][0] v0) for (int j1, kk0, v; jc[i] km; j) {if ((v a[i][j]) b[k]) k;if (g w[i] d[v][k]) {d[v][k] g w[i]; ans[v][k] {v0, k0, i};if (km !f[v][k]) q.push({v, k}), f[v][k] 1;}}}return d[b[m-1]][m];
}void path(int v, int k) {if (ans[v][k].k) path(ans[v][k].v, ans[v][k].k);cout ans[v][k].i;
}void solve() {x 0;for (int i1; it; i) {cin w[i] c[i];for (int j0, v; jc[i]; j) cin v, a[i][j] find(v);}cin n; kase;for (int i1; in; i) {cout Case kase , Trip i : Cost bfs() endl Tickets used:;path(b[m-1], m); cout endl;}
}int main() {while (cin t t) solve();return 0;
}
