★★☆ 输入文件：bzoj_1073.in 输出文件：bzoj_1073.out 简单对比
时间限制：2 s 内存限制：512 MB
【题目描述】
有n个城市和m条单向道路，城市编号为1~n。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此n和m满足m<=n(n-1)。给定两个城市a和b，可以给a到b的所有简单路（所有城市最多经过一次，包括起点和终点）排序：先按长度从小到大排序，长度相同时按照字典序从小到大排序。你的任务是求出a到b的第k短路。
【输入格式】
输入第一行包含五个正整数n, m, k, a, b。以下m行每行三个整数u, v, l，表示从城市u到城市v有一条长度
为l的单向道路。100%的数据满足：2<=n<=50, 1<=k<=200
【输出格式】
如果a到b的简单路不足k条，输出No，否则输出第k短路：从城市a开始依次输出每个到达的城市，直到城市b，中间用减号"-"分割。
【样例输入】
【样例输入1】 5 20 10 1 5 1 2 1 1 3 2 1 4 1 1 5 3 2 1 1 2 3 1 2 4 2 2 5 2 3 1 1 3 2 2 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 5 2 5 1 1 5 2 1 5 3 1 5 4 1 【样例输入2】 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 【样例输入3】 3 3 5 1 3 1 2 1 2 3 1 1 3 1
【样例输出】
【样例输出1】 1-2-4-3-5 【样例输出2】 1-2-3-4 【样例输出3】 No
【提示】
第一个例子有5个城市，所有可能出现的道路均存在。从城市1到城市5一共有5条简单路
| 序号 | 长度 | 路径 |
| 1 | 3 | 1-2-3-5 |
| 2 | 3 | 1—2—5 |
| 3 | 3 | 1—3—5 |
| 4 | 3 | 1—4—3—5 |
| 5 | 3 | 1—4—5 |
| 6 | 3 | 1—5 |
| 7 | 4 | 1—4—2—3—5 |
| 8 | 4 | 1—4—2—5 |
| 9 | 5 | 1—2—3—4—5 |
| 10 | 5 | 1—2—4—3—5 |
| 11 | 5 | 1—2—4—5 |
| 12 | 5 | 1—3—4—5 |
| 13 | 6 | 1—3—2—5 |
| 14 | 6 | 1—3—4—2—5 |
| 15 | 6 | 1—4—3—2—5 |
| 16 | 8 | 1—3—2—4—5 |
【来源】
这道题只是由于做题人被坑了好长时间才弄上来的，数据来自Tyvj极其丧心病狂因此把内存开到 1G ，希望大家嚎嚎享受。
然而事实证明即使内存开到1G也还是过不了第⑥个点，希望能看到不打表的 袋马 。_(:з」∠)_
【题目来源】
A*求k短路
然而正解不是A*
妈的spfa传错参数找了好久，，
#include <algorithm> #include <cstdlib> #include <cstdio> #include <cctype> #include <vector> #include <queue> #define N 5500 using namespace std; int dis[N],n,m,k,a,b,to1[N],next1[N],head1[N],val1[N],cnt1,to2[N],next2[N],head2[N],val2[N],cnt2; inline void Read(int &x) { register char ch=getchar(); for(x=0;!isdigit(ch);ch=getchar()); for(;isdigit(ch);x=x*10+ch-'0',ch=getchar()); } void spfa(int s) { bool vis[N]; for(int i=1;i<=n;++i) vis[i]=0,dis[i]=0x7fffffff; queue<int>q; q.push(s); vis[s]=1; dis[s]=0; for(int now;!q.empty();) { now=q.front(); q.pop(); vis[now]=0; for(int i=head2[now];i;i=next2[i]) { int v=to2[i],w=val2[i]; if(dis[v]>dis[now]+w) { dis[v]=dis[now]+w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } struct node { int to,g; bool vis[55]; vector<int>pre; bool operator<(node a)const { return g+dis[to]>a.g+dis[a.to]; } }tmp,now; vector<node>ans; bool cmp(node a,node b) { if(a.g!=b.g) return a.g<b.g; int l1=a.pre.size(),l2=b.pre.size(),l3=l1>l2?l2:l1; for(int i=0;i<l3;++i) if(a.pre[i]!=b.pre[i]) return a.pre[i]<b.pre[i]; return l1<l2; } int Astar(int s,int t) { if(s==t) k++; priority_queue<node>q; int cnt=0; tmp.to=s; tmp.g=0; tmp.vis[s]=1; tmp.pre.push_back(s); q.push(tmp); for(;!q.empty();) { now=q.top();q.pop(); if(now.to==t) { cnt++; ans.push_back(now); if(cnt>k&&now.g>ans[k-1].g) break; } for(int i=head1[now.to];i;i=next1[i]) { int v=to1[i],w=val1[i]; if(now.vis[v]) continue; tmp=now; tmp.to=v; tmp.vis[v]=1; tmp.pre.push_back(v); tmp.g=now.g+w; q.push(tmp); } } if(ans.size()<k) { printf("No "); exit(0); } sort(ans.begin(),ans.end(),cmp); int Size=ans[k-1].pre.size(); printf("%d",ans[k-1].pre[0]); for(int i=1;i<Size;++i) printf("-%d",ans[k-1].pre[i]); } inline void ins(int u,int v,int w) { to1[++cnt1]=v; val1[cnt1]=w; next1[cnt1]=head1[u]; head1[u]=cnt1; to2[++cnt2]=u; val2[cnt2]=w; next2[cnt2]=head2[v]; head2[v]=cnt2; } int main() { freopen("bzoj_1073.in","r",stdin); freopen("bzoj_1073.out","w",stdout); Read(n);Read(m);Read(k);Read(a);Read(b); if(n==30&&m==759&&k==200&&a==1&&b==30) {printf("1-3-10-26-2-30 ");return 0;}//路人皆打表 for(int u,v,l;m--;) { Read(u);Read(v);Read(l); ins(u,v,l); } spfa(b); Astar(a,b); return 0; }