1 #include<cstdio>  2 #include<cstring>  3 #define mt(a,b) memset(a,b,sizeof(a))  4 const int inf=0x3f3f3f3f;  5 class Directed_MST { ///最小树形图(有向图)  6     typedef int typec;///边权的类型  7     static const int ME=250010;///边的个数  8     static const int MV=550;///点的个数  9     struct E { 10         int u,v; 11         typec w; 12     } e[ME]; 13     int n,le,pre[MV],ID[MV],vis[MV]; 14     typec In[MV]; 15 public: 16     void init() { 17         le=0; 18     } 19     void add(int u,int v,typec w) { 20         e[le].u=u; 21         e[le].v=v; 22         e[le].w=w; 23         le++; 24     } 25     typec solve(int root,int tn) {///传入根和点的个数，点下标0开始 26         n=tn; 27         typec ret=0; 28         while(true) { 29             for(int i=0; i<n; i++) { 30                 In[i]=inf; 31             } 32             for(int i=0; i<le; i++) { 33                 int u=e[i].u; 34                 int v=e[i].v; 35                 if(e[i].w<In[v]&&u!=v) { 36                     pre[v]=u; 37                     In[v]=e[i].w; 38                 } 39             } 40             for(int i=0; i<n; i++) { 41                 if(i==root) continue; 42                 if(In[i]==inf) return -1;///除了根以外有点没有入边,则根无法到达它 43             } 44             int cntnode=0;///找环 45             mt(ID,-1); 46             mt(vis,-1); 47             In[root]=0; 48             for(int i=0; i<n; i++) { ///标记每个环 49                 ret+=In[i]; 50                 int v=i; 51                 while(vis[v]!=i&&ID[v]==-1&&v!=root) { 52                     vis[v]=i; 53                     v=pre[v]; 54                 } 55                 if(v!=root&&ID[v]==-1) { 56                     for(int u=pre[v]; u!=v; u=pre[u]) { 57                         ID[u]=cntnode; 58                     } 59                     ID[v]=cntnode++; 60                 } 61             } 62             if(!cntnode) break;///无环 63             for(int i=0; i<n; i++) { 64                 if(ID[i]==-1) { 65                     ID[i]=cntnode++; 66                 } 67             } 68             for(int i=0; i<le; i++) { ///缩点,重新标记 69                 int v=e[i].v; 70                 e[i].u=ID[e[i].u]; 71                 e[i].v=ID[e[i].v]; 72                 if(e[i].u!=e[i].v) { 73                     e[i].w-=In[v]; 74                 } 75             } 76             n=cntnode; 77             root=ID[root]; 78         } 79         return ret; 80     } 81 } gx; 82 int n,m,a[550],s[550]; 83 int main() { 84     while(~scanf("%d%d",&n,&m),n|m){ 85         for(int i=0;i<n;i++){ 86             scanf("%d",&a[i]); 87             a[i]++; 88         } 89         s[0]=0; 90         for(int i=0;i<n;i++){ 91             s[i+1]=a[i]+s[i]; 92         } 93         gx.init(); 94         for(int i=0;i<n;i++){ 95             for(int j=s[i+1]-1;j>s[i];j--){ 96                 gx.add(j,j-1,0); 97             } 98             gx.add(s[n],s[i],0); 99         }100         while(m--){101             int a,L1,b,L2,cost;102             scanf("%d%d%d%d%d",&a,&L1,&b,&L2,&cost);103             a--;104             b--;105             a=s[a]+L1;106             b=s[b]+L2;107             gx.add(a,b,cost);108         }109         printf("%d\n",gx.solve(s[n],s[n]+1));110     }111     return 0;112 }

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cstring>  4 #define mt(a,b) memset(a,b,sizeof(a))  5 using namespace std;  6 typedef __int64 LL;  7 const int inf=0x3f3f3f3f;  8 const int M=1024;  9 class Directed_MST { ///最小树形图(有向图) 10     typedef int typec;///边权的类型 11     static const int ME=M*M;///边的个数 12     static const int MV=M;///点的个数 13     struct E { 14         int u,v; 15         typec w; 16     } e[ME]; 17     int n,le,pre[MV],ID[MV],vis[MV]; 18     typec In[MV]; 19 public: 20     void init() { 21         le=0; 22     } 23     void add(int u,int v,typec w) { 24         e[le].u=u; 25         e[le].v=v; 26         e[le].w=w; 27         le++; 28     } 29     typec solve(int root,int tn) {///传入根和点的个数，点下标0开始 30         n=tn; 31         typec ret=0; 32         while(true) { 33             for(int i=0; i<n; i++) { 34                 In[i]=inf; 35             } 36             for(int i=0; i<le; i++) { 37                 int u=e[i].u; 38                 int v=e[i].v; 39                 if(e[i].w<In[v]&&u!=v) { 40                     pre[v]=u; 41                     In[v]=e[i].w; 42                 } 43             } 44             for(int i=0; i<n; i++) { 45                 if(i==root) continue; 46                 if(In[i]==inf) return -1;///除了根以外有点没有入边,则根无法到达它 47             } 48             int cntnode=0;///找环 49             mt(ID,-1); 50             mt(vis,-1); 51             In[root]=0; 52             for(int i=0; i<n; i++) { ///标记每个环 53                 ret+=In[i]; 54                 int v=i; 55                 while(vis[v]!=i&&ID[v]==-1&&v!=root) { 56                     vis[v]=i; 57                     v=pre[v]; 58                 } 59                 if(v!=root&&ID[v]==-1) { 60                     for(int u=pre[v]; u!=v; u=pre[u]) { 61                         ID[u]=cntnode; 62                     } 63                     ID[v]=cntnode++; 64                 } 65             } 66             if(!cntnode) break;///无环 67             for(int i=0; i<n; i++) { 68                 if(ID[i]==-1) { 69                     ID[i]=cntnode++; 70                 } 71             } 72             for(int i=0; i<le; i++) { ///缩点,重新标记 73                 int v=e[i].v; 74                 e[i].u=ID[e[i].u]; 75                 e[i].v=ID[e[i].v]; 76                 if(e[i].u!=e[i].v) { 77                     e[i].w-=In[v]; 78                 } 79             } 80             n=cntnode; 81             root=ID[root]; 82         } 83         return ret; 84     } 85 } gx; 86 int ha[M],hb[M],hc[M]; 87 int X,Y,Z; 88 int dist(int i, int j) { 89     int ret = abs(ha[i] - ha[j]) + abs(hb[i] - hb[j]) + abs(hc[i] - hc[j]); 90     ret *= Y; 91     if (hc[i] < hc[j]) ret += Z; 92     return ret; 93 } 94 int main(){ 95     int n; 96     while(~scanf("%d%d%d%d",&n,&X,&Y,&Z),n+X+Y+Z) { 97         n++; 98         gx.init(); 99         for (int i = 2; i <= n; i++) scanf("%d %d %d", &ha[i], &hb[i], &hc[i]);100         for (int i = 2; i <= n; i++) {101             gx.add(0,i-1,hc[i]*X);102             int k;103             scanf("%d", &k);104             while (k--) {105                 int j;106                 scanf("%d", &j);107                 j++;108                 if (j != i) {109                     int c = dist(i, j);110                     gx.add(i-1,j-1,c);111                 }112             }113         }114         int ans=gx.solve(0,n);115         if (ans==-1) puts("Impossible");116         else printf("%d\n",ans);117     }118     return 0;119 }

  1 #include<cstdio>  2 #include<cstring>  3 #include<cmath>  4 #define mt(a,b) memset(a,b,sizeof(a))  5 const int inf=0x3f3f3f3f;  6 const int M=128;  7 class Directed_MST { ///最小树形图(有向图)  8     typedef double typec;///边权的类型  9     static const int ME=M*M;///边的个数 10     static const int MV=M;///点的个数 11     struct E { 12         int u,v; 13         typec w; 14     } e[ME]; 15     int n,le,pre[MV],ID[MV],vis[MV]; 16     typec In[MV]; 17 public: 18     void init() { 19         le=0; 20     } 21     void add(int u,int v,typec w) { 22         e[le].u=u; 23         e[le].v=v; 24         e[le].w=w; 25         le++; 26     } 27     typec solve(int root,int tn) {///传入根和点的个数，点下标0开始 28         n=tn; 29         typec ret=0; 30         while(true) { 31             for(int i=0; i<n; i++) { 32                 In[i]=inf; 33             } 34             for(int i=0; i<le; i++) { 35                 int u=e[i].u; 36                 int v=e[i].v; 37                 if(e[i].w<In[v]&&u!=v) { 38                     pre[v]=u; 39                     In[v]=e[i].w; 40                 } 41             } 42             for(int i=0; i<n; i++) { 43                 if(i==root) continue; 44                 if(In[i]==inf) return -1;///除了根以外有点没有入边,则根无法到达它 45             } 46             int cntnode=0;///找环 47             mt(ID,-1); 48             mt(vis,-1); 49             In[root]=0; 50             for(int i=0; i<n; i++) { ///标记每个环 51                 ret+=In[i]; 52                 int v=i; 53                 while(vis[v]!=i&&ID[v]==-1&&v!=root) { 54                     vis[v]=i; 55                     v=pre[v]; 56                 } 57                 if(v!=root&&ID[v]==-1) { 58                     for(int u=pre[v]; u!=v; u=pre[u]) { 59                         ID[u]=cntnode; 60                     } 61                     ID[v]=cntnode++; 62                 } 63             } 64             if(!cntnode) break;///无环 65             for(int i=0; i<n; i++) { 66                 if(ID[i]==-1) { 67                     ID[i]=cntnode++; 68                 } 69             } 70             for(int i=0; i<le; i++) { ///缩点,重新标记 71                 int v=e[i].v; 72                 e[i].u=ID[e[i].u]; 73                 e[i].v=ID[e[i].v]; 74                 if(e[i].u!=e[i].v) { 75                     e[i].w-=In[v]; 76                 } 77             } 78             n=cntnode; 79             root=ID[root]; 80         } 81         return ret; 82     } 83 } gx; 84 struct point{ 85     double x,y; 86 }p[M]; 87 double Distance(point p1,point p2) { 88     return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 89 } 90 int main(){ 91     int n,m,u,v; 92     while(~scanf("%d%d",&n,&m)){ 93         for(int i=0;i<n;i++){ 94             scanf("%lf%lf",&p[i].x,&p[i].y); 95         } 96         gx.init(); 97         while(m--){ 98             scanf("%d%d",&u,&v); 99             u--;100             v--;101             gx.add(u,v,Distance(p[u],p[v]));102         }103         double ans=gx.solve(0,n);104         if(ans==-1) puts("poor snoopy");105         else printf("%.2f\n",ans);106     }107     return 0;108 }