以(i,j) 为结点建图，其中i表示目前已经到过行程单上的前i个城市，j是目前在哪个城市。
注意
1.起点是行程单上的第一个城市
2.城市的编号会很大，要重新编号。
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; #define pb(a) push(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r #define PI 3.1415926535898 template<class T> T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c)); } template<class T> T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c)); } void debug() { #ifdef ONLINE_JUDGE #else freopen("in.txt","r",stdin); //freopen("d:\out1.txt","w",stdout); #endif } int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } struct HeapNode { int d,u; bool operator < (const HeapNode &ant) const { return d>ant.d; } }; struct Edge { int from,to; int dist; int ticket_id; }; const int maxn=5005; struct Dijksta { int n; vector<int> g[maxn]; vector<Edge> edge; int done[maxn]; int d[maxn]; int p[maxn]; void init(int n) { this->n=n; for(int i=1;i<=n;i++) g[i].clear(); edge.clear(); } void add(int u,int v,int w,int id) { //if(u>maxn||v>maxn)while(1); Edge e=(Edge){u,v,w,id}; edge.push_back(e); g[u].push_back(edge.size()-1); } void solve(int s) { for(int i=1;i<=n;i++) d[i]=INF; d[s]=0; p[s]=-1; memset(done,0,sizeof(done)); priority_queue<HeapNode> q; q.push((HeapNode){0,s}); while(!q.empty()) { HeapNode x=q.top();q.pop(); if(done[x.u])continue; int u=x.u; done[u]=1; for(int i=0;i<g[u].size();i++) { Edge &e=edge[g[u][i]]; if(d[u]+e.dist<d[e.to]) { d[e.to]=d[u]+e.dist; p[e.to]=g[u][i]; q.push((HeapNode){d[e.to],e.to}); } } } } void output(int e) { stack<int> s; for(e=p[e];e!=-1;e=p[edge[e].from]) s.push(edge[e].ticket_id); if(!s.empty()&&s.top()==0)s.pop(); while(!s.empty()) printf(" %d",s.top()),s.pop(); printf(" "); } }solver; int id[11][maxn]; int n; int ID(int a,int b) { int &x=id[a][b]; if(x==0)x=++n; return x; } int ticket[22][12],iti[22][12]; int tickcost[22]; int ticnum[22],itinum[22]; int alltick,alliti; void process(int ca,int trip) { solver.init(5002); memset(id,0,sizeof(id)); n=0; for(int i=0;i<itinum[trip];i++) for(int j=1;j<=400;j++)if(i!=0||j!=iti[trip][1]) for(int k=1;k<=alltick;k++)if(ticket[k][1]==j) for(int l=2,num=i;l<=ticnum[k];l++) { if(iti[trip][num+1]==ticket[k][l])num++; solver.add(ID(i,j),ID(num,ticket[k][l]),tickcost[k],k); } solver.solve(ID(1,iti[trip][1])); int x=itinum[trip]; int idx=ID(x,iti[trip][x]); printf("Case %d, Trip %d: Cost = %d ",ca,trip,solver.d[idx]); printf(" Tickets used:"); solver.output(idx); } int readint(){int x;scanf("%d",&x);return x;} int read() { scanf("%d",&alltick); if(alltick==0)return 0; int cnt=0; map<int,int> ma; for(int i=1;i<=alltick;i++) { tickcost[i]=readint(); ticnum[i]=readint(); for(int j=1;j<=ticnum[i];j++) { int x=readint(); if(ma[x]==0)ma[x]=++cnt; ticket[i][j]=ma[x]; } } scanf("%d",&alliti); for(int i=1;i<=alliti;i++) { itinum[i]=readint(); for(int j=1;j<=itinum[i];j++) { int x=readint(); if(ma[x]==0)ma[x]=++cnt; iti[i][j]=ma[x]; } } return 1; } int main() { //debug(); int ca=0; while(read()) { ca++; for(int i=1;i<=alliti;i++) process(ca,i); } return 0; }