n<=50000个点m<=150000的带边权DAG，保证1入度0，n出度0，其他点入度出度均不为0，求：从一号点开始到n，期间有可能K<=10次随机选边走，最坏情况下总边权多少。
没理解题意系列。。问了唐神T_T题目是说，这个牛已经知道会有这种情况，所以在除了K次剩下的时间里它会选最优方案走，而如果此点最优方案比乱走方案优，那么在最坏情况下这个点也要乱走，所以在“最优”与“乱走”去min。
f[i,j]表示点i到点n，乱j次最小边权和，f[i,j]=min(max(f[k,j]+e(i,k)),min(f[k,j-1]+e(i,k))。
写bfs的话注意f定义域！！！！
1 #include2 #include 3 #include 4 #include 5 //#include 6 using namespace std; 7 8 int n,m,K; 9 #define maxm 30001110 #define maxn 5001111 struct Edge{ int to,v,next;}edge[maxm];int first[maxn],back[maxn],le=2;12 void in(int x,int y,int v,int* first) {Edge &e=edge[le];e.to=y;e.v=v;e.next=first[x];first[x]=le++;}13 #define LL long long14 int du[maxn],last[maxn];LL f[maxn][13],dis[maxn];15 int x,y,v,que[maxn],head,tail;16 const LL inf=1e15;17 void play(int x)18 {19 for (int i=back[x];i;i=edge[i].next)20 {21 const Edge &e=edge[i];22 du[e.to]--;23 if (!du[e.to]) que[tail++]=e.to;24 }25 if (x==n)26 {27 for (int i=1;i<=K;i++) f[x][i]=-inf;28 f[x][0]=0;return;29 }30 LL Max=-inf,Min=inf;31 for (int j=0;j<=K;j++)32 {33 for (int i=first[x];i;i=edge[i].next)34 {35 const Edge &e=edge[i];36 if (f[e.to][j]>=0) Max=max(Max,f[e.to][j]+e.v);37 if (j && f[e.to][j-1]>=0) Min=min(Min,f[e.to][j-1]+e.v);38 }39 f[x][j]=Max<0?(Min<0?-inf:Min):(Min<0?Max:min(Max,Min));40 }41 }42 int main()43 {44 scanf("%d%d%d",&n,&m,&K);45 memset(du,0,sizeof(du));46 for (int i=1;i<=m;i++)47 {48 scanf("%d%d%d",&x,&y,&v);49 in(x,y,v,first);50 in(y,x,v,back);51 du[x]++;52 }53 head=tail=0;54 for (int i=1;i<=n;i++) if (!du[i]) que[tail++]=i;55 while (head!=tail) play(que[head++]);56 printf("%lld\n",f[1][K]);57 return 0;58 }