The distance from one point to another is equal to the number of edges.
First select a point and connect it with other points to find the minimum distance.
Input sample #1:
4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 1
Output sample #1:
4
Input sample #2:
4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 2
Output sample #2:
5
Explain
Of course, it’s blasting.
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long int n; int m; int f[20][20]; int g[20][20]; int cnt; int tot; int ans=0x7fffffff; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline void in() { freopen("treasure.in","r",stdin); freopen("treasure.out","w",stdout); } inline void out() { fclose(stdin); fclose(stdout); } inline void Floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][k]+g[k][j],g[i][j]); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&j!=k&&k!=i) f[i][j]=min((f[i][k]+f[k][j])*g[i][j],f[i][j]); // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) // cout<<i<<" "<<j<<" "<<f[i][j]<<endl; } signed main() { in(); n=read(); m=read(); memset(f,0x3f,sizeof f); memset(g,0x3f,sizeof g); for(int x,y,z,i=1;i<=m;i++) { x=read(); y=read(); z=read(); if(x==y)continue; f[x][y]=f[y][x]=z; g[x][y]=g[y][x]=1; } Floyd(); for(int i=1;i<=n;i++) { tot=0; for(int j=1;j<=n;j++) { if(j==i) continue; tot+=f[i][j]; } ans=min(ans,tot); } put(ans); out(); return 0; }
Actually, I thought of the minimum spanning tree before that, but I found it wrong. (greedy short sighted QAQ)
Then, rqjdalao gave a niubilitiful algorithm: simulated annealing!
He can solve the shortsightedness of greed.
The introduction of randomization, in some situations, do not choose the local optimal solution, but choose the sub-optimal solution, sub-optimal solution…
Let the algorithm execute hundreds of times, take min, the probability of success is very great!
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> #include<ctime> #include<queue> using namespace std; #define int long long int dis[50]; int num[50]; int n; int m; bool vis[50]; int f[50][50]; int ans=0x7fffffff; int ls; struct node { int id; int dis; friend bool operator < (const node &a,const node &b) { return a.dis<b.dis; } }temp[50]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline void in() { freopen("treasure.in","r",stdin); freopen("treasure.out","w",stdout); } inline void out() { fclose(stdin); fclose(stdout); } inline int suiji(int i) { double x=(double)i/(double)n; double y=(double)rand()/(double)RAND_MAX; if(y*y>=x) return 2; return 1; } inline int kan_xin_qing(int k) { int tot=0LL; for(int i=1;i<=n;i++) if(!vis[i]&&dis[i]*num[i]<0x7fffffff) temp[++tot]=(node){i,dis[i]*num[i]}; sort(temp+1,temp+tot+1); if(tot<k) return temp[tot].id; return temp[k].id; } inline int Prim(int head) { for(int i=0;i<=n;i++) { vis[i]=0; dis[i]=0x3f3f3f3f; num[i]=0x3f3f3f3f; } int tot=0LL; dis[head]=num[head]=0LL; for(int i=1;i<=n;i++) { int minn=kan_xin_qing(suiji(i)); vis[minn]=true; tot+=dis[minn]*num[minn]; // cout<<tot<<" "; for(int j=1;j<=n;j++) { if(!vis[j]&&dis[j]*num[j]>f[minn][j]*(num[minn]+1)) { dis[j]=f[minn][j]; num[j]=num[minn]+1; } } } return tot; } signed main() { // in(); srand(time(0)); n=read(); m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=i==j? 0:0x3f3f3f3f; for(int x,y,z,i=1;i<=m;i++) { x=read(); y=read(); z=read(); if(x==y)continue; f[x][y]=f[y][x]=min(f[x][y],z); } for(int i=1;i<=n*800;i++) { ls=0x7fffffff; for(int j=1;j<=n;j++) ls=min(ls,Prim(j)); // cout<<ls<<" "; ans=min(ans,ls); } put(ans); out(); return 0; }
Of course, when n is so small, there is a natural way of pressing DP.
Each binary represents the current access to I.
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> #include<ctime> #include<queue> using namespace std; #define int long long int dis[50]; int n; int m; int f[50][50]; int ans=0x7fffffff; int ls; int dp[655360]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline void in() { freopen("treasure.in","r",stdin); freopen("treasure.out","w",stdout); } inline void out() { fclose(stdin); fclose(stdout); } inline void dfs(int zt) { for(int i=1;i<=n;i++) //Traverse all points { if((1<<(i-1))&zt) //If the current I has been traversed { for(int j=1;j<=n;j++) //Traversing points adjacent to I { if(!((1<<(j-1))&zt)&&f[i][j]<=0x7fffffff) //J is currently traversed and I is connected to j. { if(dp[(1<<(j-1))|zt]>dp[zt]+dis[i]*f[i][j]) //Renewable { int ls=dis[j]; dis[j]=dis[i]+1; //lsFor backtracking dp[(1<<(j-1))|zt]=dp[zt]+dis[i]*f[i][j]; //To update dfs((1<<(j-1))|zt); //Let J enter the state 0-> 1 dis[j]=ls; //To flash back } } } } } } signed main() { // in(); n=read(); m=read(); memset(f,0x5f,sizeof f); for(int x,y,z,i=1;i<=m;i++) { x=read(); y=read(); z=read(); if(x==y)continue; f[x][y]=f[y][x]=min(f[x][y],z); } for(int i=1;i<=n;i++) //Enumerate each point as the starting point. { memset(dis,0x7f,sizeof dis); //Initial value per time memset(dp,0x7f,sizeof dp); dp[1<<(i-1)]=0; //The starting point (starting point is 1, the rest is 0). dis[i]=1; dfs(1<<(i-1)); //Search from the beginning ans=min(ans,dp[(1<<n)-1]); //Final state, all 1. } put(ans); out(); return 0; }