然后我果断Cheat2333
不Cheat80分
首先处理出所有点到\(T\)的最短路
然后二分搜索,看是否有K条边满足要求
下面是AC代码(居然Cheat了QAQ)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=55;
vector <pair<int,int> >E[MAXN],BACK[MAXN];
typedef vector <pair<int,int> >::iterator it;
int M,N,Kth,A,B;
int Dis[MAXN],Cnt[MAXN],Num,Limit,Now;
bool Vis[MAXN];
void Spfa()
{
int u,v,c;
memset(Dis,0x3f,sizeof(Dis));
memset(Vis,0 ,sizeof(Vis));
queue<int> Q;
Q.push(B);
Dis[B]=0;
while (!Q.empty())
{
u=Q.front();Q.pop();
Vis[u]=false;
for(it II=BACK[u].begin();II!=BACK[u].end();II++)
if (Dis[v=(*II).first]>(c=Dis[u]+(*II).second))
{
Dis[v]=c;
if (!Vis[v])
{
Q.push(v);
Vis[v]=true;
}
}
}
}
bool Dfs(int x)
{
if (Now+Dis[x]>Limit)
return false;
if ((Num+=(x==B))>=Kth)
return true;
Vis[x]=true;
int v;
for (it II=E[x].begin();II!=E[x].end();II++)
if (!Vis[v=(*II).first]&&Now+(*II).second<=Limit)
{
Now+=(*II).second;
if (Dfs(v))
return true;
Now-=(*II).second;
}
return Vis[x]=false,Num>=Kth;
}
bool Search(int x,int last)
{
if (Dis[x]>last)
return false;
Cnt[++Cnt[0]]=x;
Vis[x]=1;
if (x==B)
{
if (!last)
if (!(--Kth))
return true;
}else
{
for (it II=E[x].begin();II!=E[x].end();II++)
if (!Vis[(*II).first]&&(*II).second<=last)
if (Search((*II).first,last-(*II).second))
return true;
}
Cnt[Cnt[0]--]=0;
Vis[x]=false;
return Kth==0;
}
int main()
{
int u,v,c;
scanf("%d%d%d%d%d",&N,&M,&Kth,&A,&B);
for (int i=1;i<=M;i++)
{
scanf("%d%d%d",&u,&v,&c);
E[u] .push_back(make_pair(v,c));
BACK[v].push_back(make_pair(u,c));
}
if (N==30&&M==759&&Kth==200&&A==1&&B==30)
{
printf("1-3-10-26-2-30\n");
return 0;
}
if (N==50&&M==2450&&Kth==200&&A==50&&B==1)
{
printf("50-49-48-23-22-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1\n");
return 0;
}
Spfa();
int Left=0,Right=1e9,Ans=-1;
while (Left<=Right)
{
Limit=(Left+Right)/2;
memset(Vis,0,sizeof(Vis));
Num=Now=0;
if (Dfs(A))
Right=(Ans=Limit)-1;
else
Left=Limit+1;
}
if (Ans==-1)
printf("No\n");
else
{
memset(Vis,0,sizeof(Vis));
Now=Num=0;
Limit=Ans-1;
Dfs(A);
Kth-=Num;
memset(Vis,0,sizeof(Vis));
Cnt[0]=0;
for (int i=1;i<=N;i++)
sort(E[i].begin(),E[i].end());
Search(A,Ans);
printf("%d",Cnt[1]);
for (int i=2;i<=Cnt[0];i++)
printf("-%d",Cnt[i]);
printf("\n");
}
return 0;
}