题目：Low Cost Air Travel
题意：
给出nt种机票，输入每张机票的价格，以及它可到达的地点。对于每张机票，只能从第一站开始乘坐，但是可以从任何一站下飞机。
再给出ni张行程表，每张行程表上包括一串地名，必需按顺序到达，但是中途可以经过其它城市作为中转。问满足每张行程单所需的最小花费以及路径。若有多种可能，输出经过城市最少的路径。
思路：
对于每一张行程单单独处理。
每一个点(i,j)代表当前在第i个地点，下一个目标是行程单上的第j个地点。
根据机票信息建图。对于同一机票上的x，y两地，假设走到x时经过了p个行程单上的点，走到y时经过了q个行程单上的点，就在(x,p)和(y,q)之间连一条边，边权为票价。
然后再跑一遍最短路就可以了。
注意：
1、地点要重新编号，不然数组会越界。
2、跑dijkstra时，在dist[x]==dist[y]时也要注意更新经过最少的地点数量。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 4000
#define maxm 20struct Node {int id,y,z;Node(int ii=0,int yy=0,int zz=-1) {id=ii,y=yy,z=zz;}bool operator < (const Node& oth) const {return id<oth.id||(id==oth.id&&y<oth.y);}
};struct Pair {int x,y,z,w;Pair(int xx=0,int yy=0,int zz=0,int ww=0) {x=xx,y=yy,z=zz,w=ww;}bool operator < (const Pair& oth) const {return y>oth.y||(y==oth.y&&z>oth.z);}
};int n,m;vector<int> tck[maxn+5];
int w[maxn+5];Node p[maxn+5];
map<Node,int> mp;
int cnt;
map<int,int> mp2;
int cnt2;int lst[maxm+5];
int spp;int dist[maxn+5];
priority_queue<Pair> que;
bool c[maxn+5];vector<Pair> g[maxn+5];Node f[maxn+5];int id(Node x) { //找到点的编号if(!mp.count(x)) mp[x]=++cnt,p[mp[x]]=x;return mp[x];
}int id(int x) { //找到数的编号if(!mp2.count(x)) mp2[x]=++cnt2;return mp2[x];
}void init() { //初始化for(int i=1; i<=maxn; i++) {tck[i].clear();}cnt2=0;mp2.clear();
}void initd() { //另一个初始化cnt=spp=0;mp.clear();for(int i=1; i<=maxn; i++) {dist[i]=1e9;g[i].clear();}memset(c,0,sizeof(c));priority_queue<Pair> emp;que=emp;memset(f,0,sizeof(f));
}int dijkstra(int s,int e) { //dijkstra求最短路 Pair ss=Pair(s,0);que.push(ss);dist[s]=0;while(!que.empty()) {Pair x=que.top();que.pop();if(c[x.x]) continue;c[x.x]=true;for(int i=0; i<g[x.x].size(); i++) {if(dist[g[x.x][i].x]==x.y+g[x.x][i].y&&(f[g[x.x][i].x].id==0||f[g[x.x][i].x].z>f[x.x].z+1))f[g[x.x][i].x]=Node(x.x,g[x.x][i].z,f[x.x].z+1);if(dist[g[x.x][i].x]>x.y+g[x.x][i].y) {dist[g[x.x][i].x]=x.y+g[x.x][i].y;que.push(Pair(g[x.x][i].x,dist[g[x.x][i].x],x.z+1,g[x.x][i].z));if(dist[g[x.x][i].x]==x.y+g[x.x][i].y)f[g[x.x][i].x]=Node(x.x,g[x.x][i].z,f[x.x].z+1);}}}return dist[e];
}void print(int ans,int t,int T,int s,int e) { //输出printf("Case %d, Trip %d: Cost = %d\n Tickets used:",T,t,ans);vector<int> ss;while(e!=s) {ss.push_back(f[e].y);e=f[e].id;}for(int i=ss.size()-1; i>=0; i--) printf(" %d",ss[i]);printf("\n");
}void readin(int& T) { //读入 T++;for(int i=1; i<=n; i++) {int nn,x;scanf("%d%d",&w[i],&nn);for(int j=1; j<=nn; j++) {scanf("%d",&x);tck[i].push_back(id(x));}}scanf("%d",&m);for(int i=1; i<=m; i++) {initd();scanf("%d",&spp);for(int j=1; j<=spp; j++) {scanf("%d",&lst[j]);lst[j]=id(lst[j]);}for(int t=1; t<=n; t++) { //使用第t张票for(int j=2; j<=spp; j++) { //下一个城市int x=tck[t][0];int nxt=j;for(int sh=1; sh<tck[t].size(); sh++) { //下车地点if(tck[t][sh]==lst[nxt]) nxt++;int y1=id(Node(x,j)),y2=id(Node(tck[t][sh],nxt));g[y1].push_back(Pair(y2,w[t],t));if(nxt==spp+1) break;}}}int s=id(Node(lst[1],2)),e=id(Node(lst[spp],spp+1));int ans=dijkstra(s,e);print(ans,i,T,s,e);}
}int main() {int t=0;while(~scanf("%d",&n)&&n) {init();readin(t);}return 0;
}