|
传送门
floyd以外无脑暴搜取得伟大胜利（得益于数据小
注释小能手又双上线了（天下苦题解不说数组是干什么用的久矣
#include<bits/stdc++.h>
#define ff(i,s,e) for(int i=s;i<=e;i++)
#define fff(i,s,e) for(int i=s;i>=e;i--)
using namespace std;
inline int read(){
register int x=0,f=1;
register char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int M=1e3*5+2;
int n,m,ans=2147383647;
int deg[M],d[M][M],nxt[M][M];//第i个点连接的点的数量 第i和第j个点之间边长 存储第i个点下一个可以连接的点们
bool vis[M][M];//搜索用，避免重复
void dfs(int st,int x,int len,int tot){//环起始点，当前点，当前环总长，当前环上点数
if(len>ans) return;//剪大枝
ff(i,1,deg[x]){//遍历与x相连的所有点
if(nxt[x][i]==st&&tot>=3){//可以成环且环上点数大于等于三，更新答案
ans=min(ans,len+d[x][nxt[x][i]]);
return;
}
if(!vis[x][nxt[x][i]]){
vis[x][nxt[x][i]]=vis[nxt[x][i]][x]=1;//注意双向标记
dfs(st,nxt[x][i],len+d[x][nxt[x][i]],tot+1);
vis[x][nxt[x][i]]=vis[nxt[x][i]][x]=0;//回溯
}
}
}
int main(){
n=read();m=read();
int u,v,dd;
ff(i,1,m){
u=read();v=read();dd=read();
if(d[u][v]==0) d[u][v]=d[v][u]=dd,nxt[u][++deg[u]]=v,nxt[v][++deg[v]]=u;
else d[u][v]=d[v][u]=min(d[u][v],dd);
//有判断是因为看到样例两点之间多个长度，直接取最小
}
ff(i,1,n){//枚举每个点作为起点
if(deg[i]){//若有点与其相连，搜
dfs(i,i,0,1);
}
}
if(ans!=2147383647) printf("%d",ans);
else printf("No solution.");
return 0;
}
emm还是正经一点补个Floyd吧
算法简介：
Floyd算法，顾名思义是Floyd研究出来的算法，是一种在图中求任意两点间最短路径的动态规划算法，适用于求解所有无负权回路的图。
时间复杂度O（n3），空间复杂度O（n2）。
由于其较高的时间复杂度，不适用于数据规模大的计算。
总结归纳两点（i，j）间最短路径，无非两种可能：从i直接经过一条边到j，或从i经过若干结点k到j。
故设f[k][i][j]为以k为中转结点时i，j间最短路径，则有递推方程式：
- f[k][i][j]=min(f[k-1][i][j]，f[k-1][i][k]+f[k-1][k][j])
利用滚动数组可优化为二维数组，即f[i][j]；
核心代码：
for(int k=1;k<=n;k++)//n为图中点的数目
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
再说一下提前操作：
1，将f数组集体赋值为无穷大，以通过min比较求最小值；
2，令f[i][i]=0，即自己和自己距离是0；
3，读入(u,v)之间边权的同时将f[u][v]更新为边权，若为无向图须双向赋值。
?回到题目，n的最大值为100决定了这道题可以用Floyd暴力求解，只需在算法基础上判断是否形成环即可。
#include<bits/stdc++.h>
#define ff(i,s,e) for(register int i=s;i<=e;i++)
#define fff(i,s,e) for(register int i=s;i>=e;i++)
using namespace std;
inline int read(){
register int x=0,f=1;
register char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=102,M=5e3+2;
int n,m,a[N][N];
int f[N][N];
int main(){
n=read(),m=read();
ff(i,1,n) ff(j,1,n) f[i][j]=a[i][j]=1e8;//赋初值，不能用memset哦
int u,v,d;
ff(i,1,m){
u=read(),v=read(),d=read();
f[u][v]=f[v][u]=a[u][v]=a[v][u]=d;//无向图，双向操作
}
ff(i,1,n) f[i][i]=0;//似乎没啥用
int ans=1e8;
ff(k,1,n){//枚举中转结点
ff(i,1,k-1){
ff(j,i+1,k-1){
ans=min(ans,f[i][j]+a[i][k]+a[k][j]);
//若无法以k作为中转结点成环，由于上面赋初值1e8的操作，ans值将不受影响
}
}
ff(i,1,n){//floyd
ff(j,1,n){
f[i][j]=f[j][i]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
if(ans==1e8) cout<<"No solution.";//判断ans值是否被更新，即是否有环
else cout<<ans;
return 0;
}
完结撒花~
|