上讲习题

AcWing 303

首先，可以知道想要接到第$i$只小猫需要什么时候出发，排序后，那么就变成了最多分成$p$部分，每部分内的费用为最后一个任务的时间分别减去前面每个任务的时间之和，求最小费用。于是设$f_{j,i}$表示前$i$只猫分成$j$部分的最小代价，则$$f_{j,i}=\min (f_{j-1,k}+a_i\times (i-k)-(s_i-s_k),0\le k<i)$$其中，我们要找一个最小的$k$使答案最小，所以$k$是变量。现在把所有变量都丢到$x$和$y$那里：$$f_{j-1,k}+s_k=a_i\times k+f_{j,i}-a_i\times i+s_i$$因为斜率（$a_i$）和横坐标（$k$）是单调递增的，所以可以不用二分，也不用判断是否在点集的外部。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int NN=1e5+4; int q[NN]; ll f[104][NN],s[NN],d[NN],a[NN]; ll get_y(int k,int i) { return f[i-1][k]+s[k]; } double doit(int x,int y,int i) { return 1.0*(get_y(x,i)-get_y(y,i))/(x-y); } int main() { int n,m,p; scanf("%d%d%d",&n,&m,&p); for(int i=2;i<=n;i++) { scanf("%lld",&d[i]); d[i]+=d[i-1]; } for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); a[i]=y-d[x]; } sort(a+1,a+m+1); for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i]; memset(f,0x3f,sizeof(f)); for(int i=0;i<=p;i++) f[i][0]=0; for(int j=1;j<=p;j++) { int h=0,t=0; q[0]=0; for(int i=1;i<=m;i++) { while(h<t&&doit(q[h+1],q[h],j)<=a[i]) h++; f[j][i]=f[j-1][q[h]]+a[i]*(i-q[h])-(s[i]-s[q[h]]); while(h<t&&doit(q[t],q[t-1],j)>=doit(i,q[t-1],j)) t--; q[++t]=i; } } printf("%lld",f[p][m]); return 0; }

概念

最短路，图论中的一个问题。指的是一个图，有起点$s$和终点$t$，中间的边有权值。要求一个从$s$到$t$的路径，使得经过的边的权值和最小。

算法

Floyd算法

方法

$Floyd$就是一个$dp$的思想，设$f_{k,i,j}$表示允许从$1...k$的点经过，从$i$到$j$的最短路。首先，不允许从任何点经过，那么只有两点直接到达，反之就不能到达。然后每次看看从新允许的$k$经过和原来的路径哪个好，即$f_{k,i,j}=\min (f_{k-1,i,j},f_{k-1,i,k}+f_{k-1,k,j})$。发现只会从$k-1$迭代，省去第一维$k$。可以解决多源最短路。 时间复杂度$\Theta (n^3)$。

判环

$Floyd$还有一个用处：判断一个有向图中是否有环。首先，自己到自己的距离设为正无穷，然后$Floyd$改成修改两点之间能否到达，即状态转移方程改成$f_{i,j}|=f_{i,k}\&f_{k,j}$。最后，如果存在一个$x$使得$f_{x,x}=0$，则说明$x$找到了一个$k$过去后又回来了，那么就是一个环。因为无向图本来过去了就可以回来，所以本方法不适用找无向图的环。

例题

AcWing 1125

题目所说的牧区就是指连通块，牧区的直径即连通块内最短距离距离最长的两个点。要求出一个连通块内最短距离距离最长的两个点，则需要计算任意两点之间的距离。因为本题是稠密图，所以用$Floyd$更优。如何计算新图的最大直径？按题目要求连接了两个牧场之后，新图的最大直径只可能是以下两种：1、原图的最大直径 ；2、新组成的牧场的直径。如果新图的最大直径就是原图的最大直径，那么新图的直径就是$\max (d_{a,b},d_{a,b}\ne +\infty )$。如果最大直径是新组成的牧场的直径，那就要求出连哪一条边能让新牧场的直径最短。设$max{x}_i$表示第$i$个点所能到达的最远的点，$le{n}_{x,y}$表示两点之间的直线距离，新加的边的端点是$a$和$b$，要求原图中$a$和$b$连接了两个牧区才需要加这条边，即$a$和$b$不连通。新连接起来的牧场的直径就是：$$max{x}_a+max{x}_b+le{n}_{a,b}$$要求出加上哪一条边得到的新牧区的直径最短，只需让原式最小即可。两种情况的最大直径中较长的一个就是新图的最大直径。另外，会不会出现新牧区的直径没有包含新边的情况呢？的确有这种可能，但是就算出现了这样的情况，也不会对答案有任何影响，因为新牧区的直径等于原来的两个牧区中直径较长的那一个，这样的话第一种情况的计算就会计算了新牧区的直径。

#include<bits/stdc++.h> using namespace std; const int NN=154; pair<double,double>p[NN]; double d[NN][NN],maxx[NN]; char g[NN][NN]; double len(int x,int y) { double lx=p[x].first-p[y].first,ly=p[x].second-p[y].second; return sqrt(lx*lx+ly*ly); } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].first,&p[i].second); for(int i=1;i<=n;i++) scanf("%s",g[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(g[i][j]=='1') d[i][j]=len(i,j); else if(i==j) d[i][j]=0; else d[i][j]=1e9; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); double ans1=0,ans2=1e9; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) if(d[i][j]!=1e9) maxx[i]=max(maxx[i],d[i][j]); ans1=max(ans1,maxx[i]); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][j]==1e9) ans2=min(ans2,maxx[i]+maxx[j]+len(i,j)); printf("%.6lf",max(ans1,ans2)); return 0; }

AcWing 343

本题是不等式，如果用$g_{i,j}=1$表示$i>j$，那么就不能出现一个环，使得环上所有边边权都是$1$，则本题就是有向图的判环。每次新加一条边，用$Floyd$判环即可。如果有一次每两个数的大小关系都确定了，即任意的$a,b$，它们两个之间一定有且仅有一个$g_{x,y}=1$（否则也是有环，在判环时已经退出了），那么就已经确定了每个点之间的关系，直接可以退出了。如果有一对$a,b$，使$g_{x,y}$都等于$0$，那么关系就没有确定，按题目要求继续计算。每一次判环执行一次$Floyd$即可，也可以增量计算。第二种时间更快，但是第一种时间已经足够了。最后考虑如何按从小到大的顺序输出这些数，因为本题范围很小，可以每一次寻找没被标记且最小的一个，输出并标记该点。考虑如何寻找最小，那么就是任何点比它大，设$visv$表示被标记了的点集，即$x\notin visv,\forall i\notin visv,g_{i,x}=1$，则$x$是最小的一个点。

#include<bits/stdc++.h> using namespace std; const int NN=26; int n,m; bool d[NN][NN],g[NN][NN],vis[NN]; void floyd() { memcpy(d,g,sizeof(d)); for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]|=d[i][k]&&d[k][j]; } int check() { for(int i=0;i<n;i++) if(d[i][i]) return 1; for(int i=0;i<n;i++) for(int j=0;j<i;j++) if(!d[i][j]&&!d[j][i]) return 0; return 2; } char getmin() { for(int i=0;i<n;i++) if(!vis[i]) { bool ok=true; for(int j=0;j<n;j++) if(!vis[j]&&d[j][i]) { ok=false; break; } if(ok) { vis[i]=true; return i+'A'; } } } int main() { while(scanf("%d%d",&n,&m)!=EOF&&n&&m) { memset(g,false,sizeof(g)); int ok=0,stop; for(int i=1;i<=m;i++) { char s[4]; scanf("%s",s); int x=s[0]-'A',y=s[2]-'A'; if(!ok) { g[x][y]=true; floyd(); ok=check(); if(ok) stop=i; } } if(!ok) puts("Sorted sequence cannot be determined."); else if(ok==1) printf("Inconsistency found after %d relations.\n",stop); else { printf("Sorted sequence determined after %d relations: ",stop); memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) printf("%c",getmin()); puts("."); } } return 0; }

dijkstra算法

方法

$dijkstra$算法是一种贪心思想，可以解决多汇最短路问题，不能处理负权边。$d_i$表示从起点到$i$，从未标记的点中找一个$d_i$最小的点$i$，更新与其相邻的点的最短路，标记点$i$。证明很复杂，在此就不多讲了。可以用堆优化，把修改了值的点放进优先级队列里即可，证明更复杂，也不多讲。 不堆优化的时间复杂度是$O(n^2)$，适合稠密图。 堆优化的时间复杂度是$O(m\log n)$，适合稀疏图。

例题

AcWing 1129

最短路板子，没有负权边，直接$dij$解决。

#include<bits/stdc++.h> using namespace std; const int NN=2504; vector<pair<int,int> >g[NN]; int d[NN]; bool vis[NN]; void dij(int s) { memset(d,0x3f,sizeof(d)); d[s]=0; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; q.push({d[s],s}); while(q.size()) { int t=q.top().second; q.pop(); vis[t]=true; for(int i=0;i<g[t].size();i++) { int v=g[t][i].first,w=g[t][i].second; if(d[v]>d[t]+w) { d[v]=d[t]+w; if(!vis[v]) q.push({d[v],v}); } } } } int main() { int n,m,s,e; scanf("%d%d%d%d",&n,&m,&s,&e); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } dij(s); printf("%d",d[e]); return 0; }

bellman-ford算法

方法

枚举$n$次，每次枚举$e$条边，用这些边更新最短路。因为如果经过了某个点，那么再经过一次是没有意义的，则最短路的边数一定不大于$n$，所以枚举$n$次即可。枚举几次就表示最多用几条边，所以也可以解决有边数限制的最短路问题。 时间复杂度$\Theta (ne)$。

例题

AcWing 345

本题就是有边数限制的最短路问题。但是题目要求的是恰好这么多条边，该怎么处理呢？很容易想到一种方法，那就是暴力转换，就是你必须找一条边迭代，否则你就无法到达。注意，以上不是正解，这个算法要开$O2$才能过（写读入优化都无法急救）。本题的正解也是最短路，将会作为习题。

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int NN=1004; struct node { int u,v,w; }edge[104]; int d1[NN],d2[NN]; int main() { int n,t,s,e; scanf("%d%d%d%d",&n,&t,&s,&e); for(int i=1;i<=t;i++) { int w,u,v; scanf("%d%d%d",&w,&u,&v); edge[i]={u,v,w}; } memset(d1,0x3f,sizeof(d1)); d1[s]=0; for(int i=1;i<=n;i++) { memcpy(d2,d1,sizeof(d1)); memset(d1,0x3f,sizeof(d1)); for(int j=1;j<=t;j++) { int u=edge[j].u,v=edge[j].v,w=edge[j].w; d1[u]=min(d1[u],d2[v]+w); d1[v]=min(d1[v],d2[u]+w); } } printf("%d",d1[e]); return 0; }

SPFA算法

方法

是$bfs$算法的最短路版本，某一个点出队时更新与它有连边的点，并将修改了值，且不在队列里的点入队。同时，这也是$bellman-ford$算法的优化版，因为只有被更新了的点才会更新其他的点。这个算法可以判断一个图有没有从源点能到的负环，只要某一个点入队$n$次及以上就是有从源点能到达的负环。有从源点能到达的负环的图就不存在最短路，或者说最短路是负无限。 时间复杂度$O(ne)$。

优化

目前常用的优化有三种：$SLF$优化、$LLL$优化和$dfs$优化。第二种是第一种的扩展，优化的时间从少到多排列。

SLF优化

改成用双端队列，如果加入时从源点到该点的距离比到队头元素的小，那么就加入到队头。时间能优化$20\%$到$30\%$。

LLL优化

要统计源点到每个点的距离的平均值，如果队头元素比平均值大就放到队尾，反之就用它。时间复杂度能优化$0\%$（有点无法到达）到$40\%$。但是如果和$SLF$优化并用是可以优化$20\%$到$55\%$。

dfs优化

就是把$spfa$的队列扩展变成$dfs$来搜。时间复杂度直接降到了$O(n)$，但是我感觉没有这么夸张。

例题

AcWing 342

这个题是一个最短路的板子题，但是因为有负权边，用$spfa$的板子即可。注意，本题有一个要求：

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从Ai到Bi，那么保证不可能通过一些道路和航线从Bi回到Ai。

这话什么意思？就是两个点通过负权边相连，那么就一定不能再通过负权边直接或间接回来。说白了：没有负环。于是我们就可以省去判负环的操作了。但是本题并不简单，因为用$spfa$很容易被卡成$\Theta (nm)$，但是这样很明显时间不够用。怎么办？考虑优化，用$SLF$就足够了。

#include<bits/stdc++.h> using namespace std; const int NN=400004; int head[NN],g[NN],nxt[NN],e[NN],vis[NN],dis[NN],tot; void add_edge(int u,int v,int w) { e[tot]=v; g[tot]=w; nxt[tot]=head[u]; head[u]=tot++; } void spfa(int s) { memset(dis,0x3f,sizeof(dis)); deque<int>q; dis[s]=0; vis[s]=true; q.push_back(s); while(q.size()) { int u=q.front(); vis[u]=false; q.pop_front(); for(int i=head[u];~i;i=nxt[i]) { int j=e[i]; if(dis[j]>dis[u]+g[i]) { dis[j]=dis[u]+g[i]; if(!vis[j]) { vis[j]=true; if(q.size()&&dis[j]<dis[q.front()]) q.push_front(j); else q.push_back(j); } } } } } int main() { int t,r,p,s; scanf("%d%d%d%d",&t,&r,&p,&s); memset(head,-1,sizeof(head)); for(int i=1;i<=r;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,w); } for(int i=1;i<=p;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); } spfa(s); for(int i=1;i<=t;i++) { if(dis[i]==0x3f3f3f3f) puts("NO PATH"); else printf("%d\n",dis[i]); } return 0; }

最短路应用

AcWing 1128

本题就相当于有无限封信，然后让这些信到处去送，最后得到信的地方收到信的时间是多久。信送达某一个点的时间肯定是最短路，那么就是要求这些最短路中最长的一个。

#include<bits/stdc++.h> using namespace std; const int NN=2504; vector<pair<int,int> >g[NN]; int d[NN]; bool vis[NN]; void dij(int s) { memset(d,0x3f,sizeof(d)); d[s]=0; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; q.push({d[s],s}); while(q.size()) { int t=q.top().second; q.pop(); vis[t]=true; for(int i=0;i<g[t].size();i++) { int v=g[t][i].first,w=g[t][i].second; if(d[v]>d[t]+w) { d[v]=d[t]+w; if(!vis[v]) q.push({d[v],v}); } } } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } dij(1); int maxx=0; for(int i=1;i<=n;i++) maxx=max(maxx,d[i]); if(maxx==0x3f3f3f3f) maxx=-1; printf("%d",maxx); return 0; }

AcWing 1127

本题可以枚举一个源点，然后从这个源点计算到其他地方的最短路之和，求一个最短的和即可。注意，本题是稀疏图，如果用$Floyd$求多源汇会超时，必须用$dij$的堆优化求。

#include<bits/stdc++.h> using namespace std; const int NN=804; vector<pair<int,int> >g[NN]; int d[NN],cow[NN],k,n,m; bool vis[NN]; int dij(int s) { memset(d,0x3f,sizeof(d)); memset(vis,false,sizeof(vis)); d[s]=0; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; q.push({d[s],s}); while(q.size()) { int t=q.top().second; q.pop(); vis[t]=true; for(int i=0;i<g[t].size();i++) { int v=g[t][i].first,w=g[t][i].second; if(d[v]>d[t]+w) { d[v]=d[t]+w; if(!vis[v]) q.push({d[v],v}); } } } int sum=0; for(int i=1;i<=k;i++) { if(d[cow[i]]==0x3f3f3f3f) return 1e9; sum+=d[cow[i]]; } return sum; } int main() { scanf("%d%d%d",&k,&n,&m); for(int i=1;i<=k;i++) scanf("%d",&cow[i]); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } int minn=1e9; for(int i=1;i<=n;i++) minn=min(minn,dij(i)); printf("%d",minn); return 0; }

AcWing 920

本题的数据范围很小，但是输入很毒瘤，用一个$stringstream$解决即可。因为边长只会是$1$，所以可以用$bfs$求最短路。

#include<bits/stdc++.h> using namespace std; const int NN=504; int sum[NN],d[NN],n,m; bool g[NN][NN]; void bfs() { memset(d,0x3f,sizeof(d)); d[1]=0; queue<int>q; q.push(1); while(q.size()) { int u=q.front(); q.pop(); for(int i=1;i<=n;i++) if(g[u][i]&&d[i]>d[u]+1) { d[i]=d[u]+1; q.push(i); } } } int main() { cin>>m>>n; for(int i=0;i<=m;i++) { string str; getline(cin,str); stringstream input(str); int cnt=0,x; while(input>>x) { cnt++; sum[cnt]=x; } for(int j=1;j<cnt;j++) for(int k=j+1;k<=cnt;k++) g[sum[j]][sum[k]]=true; } bfs(); if(d[n]==0x3f3f3f3f) cout<<"NO"; else cout<<max(d[n]-1,0); return 0; }

AcWing 1135

本题数据范围不大，可以先用$dij$求出任意两点之间的最短路。然后要访问$5$个房子，房子很少，直接累加一条遍历每个房子的最短路即可。当然，也可以只留下这几个点来一次$dij$，但是很明显暴搜就足够。

#include<bits/stdc++.h> using namespace std; const int NN=50004; vector<pair<int,int> >g[NN]; int d[10][NN],home[NN]; bool vis[NN]; void dij(int s,int d[]) { d[s]=0; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; q.push({d[s],s}); while(q.size()) { int t=q.top().second; q.pop(); vis[t]=true; for(int i=0;i<g[t].size();i++) { int v=g[t][i].first,w=g[t][i].second; if(d[v]>d[t]+w) { d[v]=d[t]+w; if(!vis[v]) q.push({d[v],v}); } } } memset(vis,false,sizeof(vis)); } int dfs(int u,int s,int cnt) { if(u>5) return cnt; int res=1e9; for(int i=1;i<=5;i++) if(!vis[i]) { vis[i]=true; res=min(res,dfs(u+1,i,cnt+d[s][home[i]])); vis[i]=false; } return res; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=5;i++) scanf("%d",&home[i]); home[0]=1; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } memset(d,0x3f,sizeof(d)); for(int i=0;i<=5;i++) dij(home[i],d[i]); printf("%d",dfs(1,0,0)); return 0; }

AcWing 1137

本题就是多源单汇最短路，可以把每个源点到距离设为$0$再求最短路即可。

#include<bits/stdc++.h> using namespace std; const int NN=1004; vector<pair<int,int> >g[NN]; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; int d[NN]; bool vis[NN]; void dij() { while(q.size()) { int t=q.top().second; q.pop(); vis[t]=true; for(int i=0;i<g[t].size();i++) { int v=g[t][i].first,w=g[t][i].second; if(d[v]>d[t]+w) { d[v]=d[t]+w; if(!vis[v]) q.push({d[v],v}); } } } } int main() { int n,m,e; while(scanf("%d%d%d",&n,&m,&e)!=EOF) { for(int i=1;i<=n;i++) g[i].clear(); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); } int w,ans=1e9; scanf("%d",&w); memset(d,0x3f,sizeof(d)); memset(vis,false,sizeof(vis)); for(int i=1;i<=w;i++) { int s; scanf("%d",&s); d[s]=0; q.push({0,s}); } dij(); printf("%d\n",d[e]==0x3f3f3f3f?-1:d[e]); } return 0; }

AcWing 1134

本题是最短路的计数问题，其实不难发现，如果一个点可以从另一个点转移过来且得到最短路，那么就可以累加到达那个点的方案数。因为边权只有$1$，可以用$bfs$做。边界条件：最开始到达起点有一种方法。

#include<bits/stdc++.h> using namespace std; const int NN=1e5+4; vector<int>g[NN]; int d[NN],cnt[NN]; bool vis[NN]; void bfs(int s) { memset(d,0x3f,sizeof(d)); d[s]=0; cnt[s]=1; vis[1]=true; queue<int>q; q.push(s); while(q.size()) { int t=q.front(); q.pop(); for(int i=0;i<g[t].size();i++) { int v=g[t][i]; if(!vis[v]) { vis[v]=true; q.push(v); d[v]=d[t]+1; } if(d[v]==d[t]+1) (cnt[v]+=cnt[t])%=100003; } } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } bfs(1); for(int i=1;i<=n;i++) printf("%d\n",cnt[i]); return 0; }

AcWing 344

本题就是在无向图中找一个最小的环。我们会用$Floyd$判断环，但是不会找最小环。于是我们又回到$Floyd$状态的定义：

设$f_{k,i,j}$表示允许从$1...k$的点经过，从$i$到$j$的最短路。

想到了什么？如果在更新之前，两点之间就能到达了，那么再加上$g_{i,k}$和$g_{k,j}$这两条边那么不就是一个环了吗？于是，每次遇到这样的情况就可以看看环是否更小，如果更小那么就更新最小环的路径，路径就是$k\to i\to j\to k$。记录一个$pat{h}_{i,j}$表示$i$到$j$的最短路是从哪里转移的，那么每次就利用$pat{h}_{i,j}$来中转，分成两部分递归输出即可。

#include<bits/stdc++.h> using namespace std; const int NN=104; int point[NN],g[NN][NN],d[NN][NN],path[NN][NN],cnt; void get_point(int x,int y) { int k=path[x][y]; if(!k) return; get_point(x,k); point[++cnt]=k; get_point(k,y); } int main() { int n,m; scanf("%d%d",&n,&m); memset(g,0x3f,sizeof(g)); for(int i=1;i<=n;i++) g[i][i]=0; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u][v]=g[v][u]=min(g[u][v],w); } int res=1e9; memcpy(d,g,sizeof(g)); for(int k=1;k<=n;k++) { for(int i=1;i<k;i++) for(int j=i+1;j<k;j++) if((long long)d[i][j]+g[i][k]+g[k][j]<res) { res=d[i][j]+g[i][k]+g[k][j]; cnt=0; point[++cnt]=k; point[++cnt]=i; get_point(i,j); point[++cnt]=j; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][j]>d[i][k]+d[k][j]) { d[i][j]=d[i][k]+d[k][j]; path[i][j]=k; } } if(res==1e9) printf("No solution."); else for(int i=1;i<=cnt;i++) printf("%d ",point[i]); return 0; }

习题

AcWing 1126

AcWing 903

AcWing 340

AcWing 341

AcWing 1131

AcWing 383

AcWing 345

解析和代码在下一篇博客——最小生成树给出