\u5c31\u662f\u4e00\u4e2a\u65e0\u5411\u56fe\u627evs\u5230vt\u7684\u7b2cK\u957f\u7b80\u5355\u8def\u3002\u3002
\u8fd9\u4e2a\u5b9e\u9645\u4e0a\u76f4\u63a5\u4e8c\u5206+\u526a\u679d\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u5173\u952e\u662f\u9898\u76ee\u4e00\u6a21\u4e00\u6837\u7684SCOI 2007 \u7684kshort(\u8fd9\u4e2a\u7684\u6570\u636e\u8303\u56f4\u53cd\u800c\u5c0f\u6655\u3002\u3002)\u53cd\u800cA\u4e0d\u6389\u3002\u3002\u56e7\u554a\u56e7\u3002\u3002\u3002\u3002
\u4e8c\u5206K\u77ed\u8def\u7684\u957f\u5ea6\uff0c\u7136\u540edfs\u5224\u65ad\u662f\u5426\u5b58\u5728K\u6761\u5c0f\u4e8e\u8fd9\u4e2a\u957f\u5ea6\u7684\u8def\u5f84\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u77e5\u9053K\u957f\u8def\u7684\u957f\u5ea6\uff0c\u7136\u540e\u751f\u6210\u6240\u6709\u8fd9\u4e9b\u8def\uff0c\u6392\u4e2a\u5e8f\u5c31\u53ef\u4ee5\u4e86\u6655\u3002\u3002
Code\uff1a
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
#include<cstring>
#define pb push_back
using namespace std;
const int maxn=100,inf=~0U>>2;
int n,m,k,vs,vt;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void AddEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));
E[t].pb(Edge(s,c));
}
int Dist[maxn];
void Spfa(int vs,vector<Edge> E[maxn])
{
bool inq[maxn]={0};queue<int> Q;
for(int i=0;i<n;i++) Dist[i]=inf;
Dist[vs]=0;inq[vs]=true;Q.push(vs);
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;
int cost=Dist[t],ncost;
for(eit e=E[t].begin();e!=E[t].end();++e)
if((ncost=cost+e->c)<Dist[e->t])
{ Dist[e->t]=ncost;
if(!inq[e->t])
inq[e->t]=true,Q.push(e->t);
}
}
}
bool vis[maxn]={0};
int Limit,Num;
void dfs(int no,int gone)
{
vis[no]=true;
if(Num>=k)goto end;
if(gone+Dist[no]>Limit) goto end;
if(no==vt){Num++;goto end;}
for(eit e=E[no].begin();e!=E[no].end();++e)if(!vis[e->t])
{
dfs(e->t,gone+e->c);
if(Num>=k) goto end;
}
end:
vis[no]=false;
}
int Now[maxn];
struct Route
{
int*A;
int n,Len;
Route(int _n,int _Len)
{
n=_n;Len=_Len;
A=new int[n];
memcpy(A,Now,sizeof(int)*n);
}
bool operator<(const Route&o)const
{
return Len<o.Len;
}
void show()const
{
cout<<Len<<" "<<n<<endl;
for(int i=0;i<n-1;i++)
cout<<A[i]+1<<" ";
cout<<A[n-1]+1<<endl;
}
};
vector<Route> Rs;
void Sdfs(int no,int gone,int d)
{
vis[no]=true;
Now[d-1]=no;
if(gone+Dist[no]>Limit) goto end;
if(no==vt)
{
Rs.pb(Route(d,gone));
goto end;
}
for(eit e=E[no].begin();e!=E[no].end();++e)if(!vis[e->t])
{
Sdfs(e->t,gone+e->c,d+1);
}
end:
vis[no]=false;
}
bool Check(int _Limit)
{
Num=0;
Limit=_Limit;
dfs(vs,0);
return Num>=k;
}
void Get(int _Limit)
{
Limit=_Limit;
Sdfs(vs,0,1);
sort(Rs.begin(),Rs.end());
Rs[k-1].show();
}
void Init()
{
cin>>n>>m>>k;
int s,t,c;
while(m–)
{
cin>>s>>t>>c;s–;t–;
AddEdge(s,t,c);
}
cin>>vs>>vt;vs–;vt–;
}
void Work()
{
Spfa(vt,E);
int l=0,r=inf;
if(!Check(r))
{
cout<<"No"<<endl;
return;
}
while(l+1<r)
{
int m=l+r>>1;
if(Check(m))
r=m;
else
l=m;
}
Get(r);
}
int main()
{
\/\/freopen("in","r",stdin);
Init();
Work();
}<\/p>\n","protected":false},"excerpt":{"rendered":"
\u5c31\u662f\u4e00\u4e2a\u65e0\u5411\u56fe\u627evs\u5230vt\u7684\u7b2cK\u957f\u7b80\u5355\u8def\u3002\u3002\u8fd9\u4e2a\u5b9e\u9645\u4e0a\u76f4\u63a5\u4e8c\u5206+\u526a\u679d\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u5173\u952e\u662f\u9898\u76ee\u4e00\u6a21\u4e00\u6837\u7684SCOI 2007 \u7684kshort(\u8fd9\u4e2a\u7684\u6570\u636e\u8303\u56f4\u53cd\u800c\u5c0f\u6655\u3002\u3002)\u53cd\u800cA\u4e0d\u6389\u3002\u3002\u56e7\u554a\u56e7\u3002\u3002\u3002\u3002\u4e8c\u5206K\u77ed\u8def\u7684\u957f\u5ea6\uff0c\u7136\u540edfs\u5224\u65ad\u662f\u5426\u5b58\u5728K\u6761\u5c0f\u4e8e\u8fd9\u4e2a\u957f\u5ea6\u7684\u8def\u5f84\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u77e5\u9053K\u957f\u8def\u7684\u957f\u5ea6\uff0c\u7136\u540e\u751f\u6210\u6240\u6709\u8fd9\u4e9b\u8def\uff0c\u6392\u4e2a\u5e8f\u5c31\u53ef\u4ee5\u4e86\u6655\u3002\u3002Code\uff1a#include<algorithm>#include<vector>#include<iostream>#include<queue>#include<cstring>#define pb push_backusing namespace std;const int maxn=100,inf=~0U>>2;int n,m,k,vs,vt;struct Edge{ int t,c; Edge(int _t,int _c):t(_t),c(_c){}};vector<Edge> E[maxn];typedef vector<Edge>::iterator eit;void AddEdge(int s,int t,int c){ E[s].pb(Edge(t,c)); E[t].pb(Edge(s,c));}int Dist[maxn];void Spfa(int vs,vector<Edge> E[maxn]){ bool inq[maxn]={0};queue<int> Q; for(int i=0;i<n;i++) Dist[i]=inf; Dist[vs]=0;inq[vs]=true;Q.push(vs); while(Q.size()) { int t=Q.front();Q.pop();inq[t]=false; int cost=Dist[t],ncost; for(eit e=E[t].begin();e!=E[t].end();++e) if((ncost=cost+e->c)<Dist[e->t]) { Dist[e->t]=ncost; if(!inq[e->t]) inq[e->t]=true,Q.push(e->t); } }}bool vis[maxn]={0};int Limit,Num;void dfs(int no,int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/222"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=222"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/222\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=222"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=222"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=222"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}