最近脑子有点乱 老是不想清楚就啪啪的敲 敲完之后一看 咦。。样例都过不去 仔细一想 这样不对啊
刚开始就写了一SPFA 最后发现边跟点的关系没处理好 删了。。写dfs。。还是没转化好 开始搜解题方法 看到别人都说最小环 解最小环的方法跟我想的差不多 就是边转化点没处理好
又想了想 开个二维数组标记下 转化点 然后就枚举每条边的两个点间的最短距离 要先删了这条边 找个最小的就好了
dijk求最短路
1 /* 2 ID: shangca2 3 LANG: C++ 4 TASK: fence6 5 */ 6 #include <iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<algorithm> 10 #include<stdlib.h> 11 using namespace std; 12 #define N 110 13 #define INF 0xfffffff 14 int f[N][N],w[N][N],t,o[N][3],vis[N],dis[N]; 15 int n; 16 int init(int a,int c) 17 { 18 int i,u[10],k=0; 19 for(i = 1; i <= c ; i++) 20 { 21 cin>>u[i]; 22 if(f[a][u[i]]) 23 k = f[a][u[i]]; 24 } 25 if(k==0) 26 { 27 t++; 28 k = t; 29 } 30 for(i = 1; i <= c ; i++) 31 f[u[i]][a] = k; 32 return k; 33 } 34 int dijk(int s,int e) 35 { 36 memset(vis,0,sizeof(vis)); 37 int minz,k,i,j; 38 for(i = 1 ;i <= t ; i++) 39 dis[i] = INF; 40 dis[s] = 0; 41 for(i =1 ; i <= t ; i++) 42 { 43 minz = INF; 44 for(j = 1; j <= t ;j++) 45 if(!vis[j]&&dis[j]<minz) 46 minz = dis[k=j]; 47 vis[k] = 1; 48 for(j = 1 ; j <= t ; j++) 49 if(w[k][j]+dis[k]<dis[j]) 50 dis[j] = w[k][j]+dis[k]; 51 } 52 return dis[e]; 53 } 54 int main() 55 { 56 freopen("fence6.in","r",stdin); 57 freopen("fence6.out","w",stdout); 58 int i,a,b,c,d; 59 cin>>n; 60 memset(w,127,sizeof(w)); 61 for(i = 1; i <= n ; i++) 62 { 63 cin>>a>>b>>c>>d; 64 int u = init(a,c); 65 int v = init(a,d); 66 w[u][v] = b; 67 w[v][u] = b; 68 o[i][0] = u; 69 o[i][1] = v; 70 o[i][2] = b; 71 } 72 int ans = INF; 73 for(i = 1; i <= n ; i++) 74 { 75 int u = o[i][0]; 76 int v = o[i][1]; 77 w[u][v] = INF; 78 w[v][u] = INF; 79 ans = min(ans,dijk(u,v)+o[i][2]); 80 w[u][v] = o[i][2]; 81 } 82 cout<<ans<<endl; 83 return 0; 84 }