题目描述
题解：
明显的$k$短路问题，这里提供两种方法。
1.$A$*算法
$A$*可以解决一般的$k$短路问题，但是并不如可持久化可并堆优秀。
$A$*的本质是$f+g$，而估价函数可以用终止节点到终点的最短路表示。
所以先反向建图$dij$，然后小根堆跑$A$*即可。
优化一下，总代价/起点终点最短路就是每个点经过的最大次数。
代码：
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 5050; const int M = 200050; const double eps = 1e-8; template<typename T> inline void read(T&x) {T f = 1,c = 0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}x = f*c; } int n,m,hed[N],cnt,heb[N],cnb; double lim; struct EG {int to,nxt;double w; }e[2*M],br[2*M]; void ae(int f,int t,double w) {e[++cnt].to = t;e[cnt].nxt = hed[f];e[cnt].w = w;hed[f] = cnt; } void ab(int f,int t,double w) {br[++cnb].to = t;br[cnb].nxt = heb[f];br[cnb].w = w;heb[f] = cnb; } double g[N]; bool vis[N]; struct Pair {int x;double d;Pair(){}Pair(int x,double d):x(x),d(d){}friend bool operator < (Pair a,Pair b){return a.d>b.d;} }tp; void dij() {priority_queue<Pair>q;for(int i=1;i<n;i++)g[i]=1e18;q.push(Pair(n,0.0));while(!q.empty()){tp = q.top();q.pop();int u = tp.x;if(vis[u])continue;vis[u] = 1;for(int j=heb[u];j;j=br[j].nxt){int to = br[j].to;if(g[to]-g[u]-br[j].w>eps){g[to] = g[u]+br[j].w;q.push(Pair(to,g[to]));}}} } int ans,t[N]; void A_star() {priority_queue<Pair>q;q.push(Pair(1,g[1]));int kk = (int)(lim/g[1])+1;while(!q.empty()){tp = q.top();q.pop();int u = tp.x;if(lim-tp.d+eps<0)break;if(u==n){lim-=tp.d;ans++;continue;}t[u]++;if(t[u]>kk)continue;for(int j=hed[u];j;j=e[j].nxt){int to = e[j].to;if(lim-(tp.d-g[u]+e[j].w+g[to])+eps>0){q.push(Pair(to,tp.d-g[u]+e[j].w+g[to]));}}} } int main() {read(n),read(m);scanf("%lf",&lim);if(lim>1000000){puts("2002000");return 0;}int f,t;double w;for(int i=1;i<=m;i++){read(f),read(t);scanf("%lf",&w);ae(f,t,w);ab(t,f,w);}dij();A_star();printf("%d\n",ans);return 0; }
2.可持久化可并堆
这绝壁是个柯学做法。
先放大牛$pdf$。
先建出最短路树。
对于每条非树边，我们都能得到经过这条边至少多绕多远。
对于一种绕远方案，方案总长=起点终点最短路+多绕的距离。
由于一个点沿最短路树边向终点移动时并不会绕远，所以它可以自由“向上”移动。
所以先对于每个点处理从该点出发的非树边，将其放入小根堆中，
然后$dfs$/按拓扑序从树根到叶节点合并小根堆。
最后用一个小根堆维护就好了。
代码：
/**************************************************************Problem: 1975User: LiGuanlinLanguage: C++Result: AcceptedTime:600 msMemory:56784 kb ****************************************************************/#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 5050; const int M = 200050; const int MAXN = 10*M; const double eps = 1e-8; template<typename T> inline void read(T&x) {T f = 1,c = 0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}x = f*c; } int n,m,fa[N],tot,rt[N],pre[N]; double lim,g[N]; bool vis[N]; struct node {int ls,rs,dis,tl;double v; }p[MAXN]; int merge(int x,int y) {if(!x||!y)return x+y;if(p[x].v-p[y].v>=eps)swap(x,y);int u = ++tot;p[u] = p[x];p[u].rs = merge(p[u].rs,y);if(p[p[u].ls].dis<p[p[u].rs].dis)swap(p[u].ls,p[u].rs);p[u].dis = p[p[u].rs].dis+1;return u; } struct Pair {int x;double d;Pair(){}Pair(int x,double d):x(x),d(d){}friend bool operator < (Pair a,Pair b){return a.d>b.d;} }tp; int hed[N],cnt=1; bool cov[2*M]; struct EG {int to,nxt;double w; }e[2*M]; void ae(int f,int t,double w) {e[++cnt].to = t;e[cnt].nxt = hed[f];e[cnt].w = w;hed[f] = cnt; } void dij() {priority_queue<Pair>q;for(int i=1;i<n;i++)g[i]=1e18;q.push(Pair(n,0.0));while(!q.empty()){tp = q.top();q.pop();int u = tp.x;if(vis[u])continue;vis[u] = 1;for(int j=hed[u];j;j=e[j].nxt){if(j&1){int to = e[j].to;if(g[to]+eps>g[u]+e[j].w){g[to] = g[u]+e[j].w;q.push(Pair(to,g[to]));}}}} } void dfs(int u) {vis[u] = 1;for(int j=hed[u];j;j=e[j].nxt)if(j&1){int to = e[j].to;if(fabs(g[to]-(e[j].w+g[u]))<=eps&&!vis[to]){fa[to] = u;cov[j^1] = 1;dfs(to);}} } void topo() {priority_queue<Pair>q;for(int i=1;i<=n;i++)q.push(Pair(i,g[i]));for(int u,i=1;i<=n;i++){u = q.top().x;q.pop();if(fa[u])rt[u] = merge(rt[u],rt[fa[u]]);} } int main() {read(n),read(m);scanf("%lf",&lim);int f,t;double w;for(int i=1;i<=m;i++){read(f),read(t);scanf("%lf",&w);ae(f,t,w);ae(t,f,w);}dij();memset(vis,0,sizeof(vis));dfs(n);for(int j=2;j<=cnt;j+=2){if(!cov[j]){int f = e[j^1].to,t = e[j].to;double w = g[t]+e[j].w-g[f];p[++tot].v = w,p[tot].dis = 1,p[tot].tl = t;rt[f] = merge(rt[f],tot);}}topo();priority_queue<Pair>q;int ans = 0;if(lim+eps>g[1])lim-=g[1],ans++;if(rt[1])q.push(Pair(rt[1],p[rt[1]].v));while(!q.empty()){tp = q.top();q.pop();if(lim+eps>tp.d+g[1])lim-=(tp.d+g[1]),ans++;else break;int u = tp.x,ls = p[u].ls,rs = p[u].rs;if(ls)q.push(Pair(ls,tp.d-p[u].v+p[ls].v));if(rs)q.push(Pair(rs,tp.d-p[u].v+p[rs].v));int t = p[u].tl;if(rt[t])q.push(Pair(rt[t],p[rt[t]].v+tp.d));}printf("%d\n",ans);return 0; }
