T1
floyd 模板。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[131][131];
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
int main(){
cin>>n>>m,memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,dp[u][v]=dp[v][u]=w;
floyd();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cout<<dp[i][j]<<' ';
cout<<'\n';
}
return 0;
}
T2
边权改为欧几里得距离即可。
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int n,m,s,t;
double dp[131][131];
pair<int,int> p[131];
double dis(double x,double y,double xx,double yy){
return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=1e9;
for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y,dp[i][i]=0;
cin>>m;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,dp[u][v]=dp[v][u]=dis(p[u].x,p[u].y,p[v].x,p[v].y);
cin>>s>>t;
floyd();
cout<<setprecision(2)<<fixed<<dp[s][t];
return 0;
}
T3
枚举集合位置，用 floyd 预处理最短路求和取 \(\min\) 即可。
对于 hack 数据，我们需要将初始值设小，不然在不连通的情况下求和会爆 int。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p,c;
int ans=1e9;
int dp[831][831];
int a[531];
void floyd(){
for(int k=1;k<=p;k++)
for(int i=1;i<=p;i++)
for(int j=1;j<=p;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
signed main(){
cin>>n>>p>>c;
for(int i=1;i<=p;i++)
for(int j=1;j<=p;j++)
dp[i][j]=10000;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=p;i++) dp[i][i]=0;
for(int i=1,u,v,w;i<=c;i++) cin>>u>>v>>w,dp[u][v]=dp[v][u]=w;
floyd();
for(int i=1;i<=p;i++){
int s=0;
for(int j=1;j<=n;j++) s+=dp[i][a[j]];
ans=min(ans,s);
}
cout<<ans;
return 0;
}
T4
依题建树跑 floyd 即可。
#include<bits/stdc++.h>
using namespace std;
int n,ans=1e9;
int w[131],dp[131][131];
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
int main(){
cin>>n;
memset(dp,0x3f,sizeof(dp));
for(int i=1,u,v;i<=n;i++){
cin>>w[i]>>u>>v;
if(u) dp[i][u]=dp[u][i]=1;
if(v) dp[i][v]=dp[v][i]=1;
dp[i][i]=0;
}
floyd();
for(int i=1;i<=n;i++){
int s=0;
for(int j=1;j<=n;j++) s+=dp[i][j]*w[j];
ans=min(ans,s);
}
cout<<ans;
return 0;
}
习题 T1
转移方程改为 \(dis_{i,j}=\min(dis_{i,j},\max(dis_{i,k},dis_{k,j}))\) 即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t;
int ans=1e9;
int dp[331][331];
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));
}
signed main(){
cin>>n>>m>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=1e9;
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=1,u,v,w;i<=m;i++)
cin>>u>>v>>w,dp[u][v]=w;
floyd();
for(int i=1,u,v;i<=t;i++)
cin>>u>>v,cout<<(dp[u][v]==1e9?-1:dp[u][v])<<'\n';
return 0;
}
习题 T2
上题的双倍经验，只不过放到了无向图上。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t,tot;
int ans=1e9;
int dp[331][331];
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));
}
signed main(){
//freopen("qq.out","w",stdout);
while(cin>>n>>m>>t&&n&&m&&t){
cout<<"Case #"<<++tot<<'\n';
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=1e9;
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=1,u,v,w;i<=m;i++)
cin>>u>>v>>w,dp[u][v]=dp[v][u]=w;
floyd();
for(int i=1,u,v;i<=t;i++){
cin>>u>>v;
if(dp[u][v]==1e9) cout<<"no path\n";
else cout<<dp[u][v]<<'\n';
}
cout<<'\n';
}
return 0;
}