/*    给出一张无向图，现在求一个点，使得这个点到所有点的距离和最小    输出这个点的编号和距离和*/#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int N=10,INF=0x3f3f3f3f;int n,d[N][N],c,x,y,m;int main(){    while(~scanf("%d",&m),m){        memset(d,INF,sizeof(d)); n=0;        while(m--){            scanf("%d%d%d",&x,&y,&c);            d[x][y]=d[y][x]=c;            n=max(n,max(x,y));        }        for(int k=0;k<=n;k++)            for(int i=0;i<=n;i++)                for(int j=0;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);        int ans=INF,pos=0;        for(int i=0;i<=n;i++){            int tmp=0;            for(int j=0;j<=n;j++)if(i!=j)tmp+=d[i][j];            if(tmp<ans)ans=tmp,pos=i;        }printf("%d %d\n",pos,ans);    }return 0;}

/*    求一头奶牛到其它奶牛的平均距离的100倍的最小值*/#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int N=310,INF=0x3f3f3f3f;int n,d[N][N],c,x,y,m,a[N];int main(){    while(~scanf("%d%d",&n,&m)){        memset(d,INF,sizeof(d));         while(m--){            scanf("%d",&c);            for(int i=1;i<=c;i++)scanf("%d",&a[i]),a[i]--;            for(int i=1;i<=c;i++)for(int j=1;j<i;j++)d[a[i]][a[j]]=d[a[j]][a[i]]=1;        }        for(int k=0;k<n;k++)            for(int i=0;i<n;i++)                for(int j=0;j<n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);        int ans=INF;        for(int i=0;i<n;i++){            int tmp=0;            for(int j=0;j<n;j++)if(i!=j)tmp+=d[i][j];            if(tmp<ans)ans=tmp;        }printf("%d\n",100*ans/(n-1));    }return 0;}

/*    在有向图中求每个点到终点后返回的最短路的最大值    以终点为源点做一次正向路径的spfa和一次反向路径的spfa，    相加即为每个点的答案*/#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=200010,inf=~0U>>2,M=200000;int T,tim[N],q[N],size,h,t,n,m,x,ed[2],dis[2][N],in[N],nxt[2][N],w[2][N],v[2][N],g[2][N],u,e,cost;void add(int u,int x,int y,int z){v[u][++ed[u]]=y;w[u][ed[u]]=z;nxt[u][ed[u]]=g[u][x];g[u][x]=ed[u];}int spfa(int u,int S){    for(int i=1;i<=n;i++)dis[u][i]=inf,in[i]=0,tim[i]=0;    tim[S]=1,dis[u][S]=0,in[S]=1;    int i,x,size; q[h=t=size=1]=S;    while(size){        for(i=g[u][x=q[h]],h=(h+1)%M,size--;i;i=nxt[u][i])if(dis[u][x]+w[u][i]<dis[u][v[u][i]]){            dis[u][v[u][i]]=dis[u][x]+w[u][i];            if(!in[v[u][i]]){                tim[v[u][i]]++,t=(t+1)%M,size++,in[q[t]=v[u][i]]=1;                if(tim[v[u][i]]>n)return -1;            }        }in[x]=0;    }}int main(){    scanf("%d%d%d",&n,&m,&x);    for(int i=1;i<=m;i++){        scanf("%d%d%d",&u,&e,&cost);        add(0,u,e,cost);        add(1,e,u,cost);        }spfa(1,x);spfa(0,x);    int ans=0;    for(int i=1;i<=n;i++)ans=max(dis[0][i]+dis[1][i],ans);    return printf("%d\n",ans),0;}

/*    给出一张n个点m条边的无向图，有w个虫洞，可以在穿越的过程中减少时间    问有没有可能回到过去    回到过去即存在负权回路，SPFA求解即可    需要注意的是不是连通图，因此在做spfa的时候要将所有的点先入队一次*/#include <cstdio>#include <cstring>using namespace std;const int N=200010,inf=~0U>>2,M=200000;int x,S,T,time[N],q[N],size,h,t,n,m,W,ed,dis[N],in[N],nxt[N],w[N],v[N],g[N],u,e,cost;void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}int spfa(int S){    for(int i=1;i<=n;i++)dis[i]=inf,in[i]=0,time[i]=0;    time[S]=1,dis[S]=0,in[S]=1;    int i,x,size; q[h=t=size=1]=S;    for(int i=1;i<=n;i++){time[i]++,t=(t+1)%M,size++,in[q[t]=i]=1;}    while(size){        for(i=g[x=q[h]],h=(h+1)%M,size--;i;i=nxt[i])if(dis[x]+w[i]<dis[v[i]]){            dis[v[i]]=dis[x]+w[i];            if(!in[v[i]]){                time[v[i]]++,t=(t+1)%M,size++,in[q[t]=v[i]]=1;                if(time[v[i]]>n)return -1;            }        }in[x]=0;    }return dis[T];}int cas;int main(){    scanf("%d",&cas);    while(cas--){        scanf("%d%d%d",&n,&m,&W);        memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt));        memset(w,0,sizeof(w)); memset(g,0,sizeof(g)); ed=0;        for(int i=1;i<=m;i++){            scanf("%d%d%d",&u,&e,&cost);            add(u,e,cost);            add(e,u,cost);        }        for(int i=1;i<=W;i++){            scanf("%d%d%d",&u,&e,&cost);            add(u,e,-cost);        }        if(spfa(1)==-1)puts("YES");         else puts("NO");    }return 0;}

/*    建造每条道路需要的费用已经给出，    现在求在起点到每个点都是最短路的情况下的最小修路费用    考虑到最后一定是树形的，因此只要保留每个点与其父节点之间的边的费用最小值即可    在计算最短路的同时不断更新费用*/#include <cstdio>  #include <cstring> #include <queue> #include <utility> using namespace std;  const int N=2000100;  const int INF=~0U>>2;  typedef pair<int,int>seg;  priority_queue<seg,vector<seg>,greater<seg> >q;     int d[N],D[N],head[N],u[N],v[N],w[N],nxt[N],cost[N],n,m,a,b,c,cc,ed=0,H,x[N],y[N]; bool vis[N];  void add(int a,int b,int c,int cos){      u[++ed]=a,v[ed]=b,w[ed]=c;cost[ed]=cos;    nxt[ed]=head[u[ed]]; head[u[ed]]=ed;     }     void Dijkstra(int src){      memset(vis,0,sizeof(vis));      for(int i=1;i<=n;i++)d[i]=INF;      d[src]=0;      q.push(make_pair(d[src],src));      while(!q.empty()){          seg now=q.top(); q.pop();          int x=now.second;          if(d[x]<now.first)continue;         for(int e=head[x];e!=-1;e=nxt[e])         if(d[v[e]]>d[x]+w[e]){             d[v[e]]=d[x]+w[e];              D[v[e]]=cost[e];            q.push(make_pair(d[v[e]],v[e]));          }else if(d[v[e]]==d[x]+w[e]){            D[v[e]]=min(cost[e],D[v[e]]);        }    }} int main(){	  while(~scanf("%d%d",&n,&m),m+n){		    memset(head,-1,sizeof(head));ed=0;		    memset(nxt,-1,sizeof(nxt));	      while(m--){	    	    scanf("%d%d%d%d",&a,&b,&c,&cc);	    	    add(a,b,c,cc);add(b,a,c,cc);	      }Dijkstra(1);	      int ans=0;	      for(int i=2;i<=n;i++)ans+=D[i];		    printf("%d\n",ans);	  }return 0;}

/*    一张图中有陆路和水路，水路必须要有船才能走，当船开到x点时就会停在x点    一开始人和船都在1点，问按给出顺序访问一些点需要的最短时间    利用floyd可以得出只走陆路和只走水路时两点间的最短路    dp[i][j]表示走到了第i个需要访问的村庄，船停在j点的最短路，然后顺序dp更新状态即可*/#include <cstdio>#include <algorithm>#include <cstring> #define rep(i,n) for(int i=1;i<=n;i++)using namespace std;typedef long long LL;const int INF=0x3f3f3f3f;int n,m,q,x,y,z,d[1010]; char c;int dl[210][210],ds[210][210],dp[1010][210];int main(){    while(~scanf("%d%d",&n,&m),n+m){        rep(i,n)rep(j,n)ds[i][j]=dl[i][j]=i==j?0:INF;        rep(i,m){            scanf("%d%d%d %c",&x,&y,&z,&c);            if(c==‘S‘)ds[x][y]=ds[y][x]=min(ds[x][y],z);            else dl[x][y]=dl[y][x]=min(dl[x][y],z);        }scanf("%d",&q);        rep(i,q)scanf("%d",d+i);        rep(k,n)rep(i,n)rep(j,n){            ds[i][j]=min(ds[i][j],ds[i][k]+ds[k][j]);            dl[i][j]=min(dl[i][j],dl[i][k]+dl[k][j]);        }memset(dp,INF,sizeof(dp));        dp[1][d[1]]=0;        rep(i,q)rep(j,n){            dp[i][j]=min(dp[i][j],dp[i-1][j]+dl[d[i-1]][d[i]]);            rep(k,n)dp[i][k]=                min((LL)dp[i][k],(LL)dp[i-1][j]+dl[d[i-1]][j]+ds[j][k]+dl[k][d[i]]);          }printf("%d\n",*min_element(dp[q],dp[q]+n+1));    }return 0;}

/*    裸最小生成树*/#include <cstdio>#include <algorithm>using namespace std;struct data{int x,y,c;}p[20010];  int n,m,f[110],x;bool cmp(data a,data b){return a.c<b.c;}int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}int main(){      while(~scanf("%d",&n)){    	  m=0;        for(int i=1;i<=n;i++)f[i]=i;         for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){            scanf("%d",&x);            if(i<j){p[++m].c=x;p[m].x=i;p[m].y=j;}        }sort(p+1,p+m+1,cmp);        int ans=0;        for(int i=1;i<=m;i++){            if(sf(p[i].x)!=sf(p[i].y)){                ans+=p[i].c;                f[sf(p[i].x)]=sf(p[i].y);            }        }printf("%d\n",ans);	  }return 0;  }  

/*    裸最大生成树，需要注意判断无解的情况*/#include <cstdio>#include <algorithm>using namespace std;struct data{int x,y,c;}p[20010];  int n,m,f[1010],x;bool cmp(data a,data b){return a.c>b.c;}int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}int main(){    while(~scanf("%d%d",&n,&m)){        for(int i=1;i<=n;i++)f[i]=i;        for(int i=1;i<=m;i++){            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);        }sort(p+1,p+m+1,cmp);        int ans=0,cnt=1;        for(int i=1;i<=m;i++){            if(sf(p[i].x)!=sf(p[i].y)){                ans+=p[i].c;                cnt++;                f[sf(p[i].x)]=sf(p[i].y);            }        }if(cnt!=n)puts("-1");        else printf("%d\n",ans);    }return 0;}

/*    删除一些边使得图中没有环，求删除边的最小代价*/#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int N=100100;int n,m,a,b,x[N],y[N],f[N];struct data{int x,y;double c;}p[N];bool cmp(data a,data b){return a.c<b.c;}int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}int sqr(int x){return x*x;}int main(){    while(~scanf("%d%d",&n,&m)){        double sum=0;        for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]),f[i]=i;        for(int i=1;i<=m;i++){            scanf("%d%d",&a,&b);            double c=sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));            sum+=c;            p[i].x=a;p[i].y=b;            p[i].c=-c;        }sort(p+1,p+m+1,cmp);        for(int i=1;i<=m;i++){            if(sf(p[i].x)!=sf(p[i].y)){                sum+=p[i].c;                f[sf(p[i].x)]=sf(p[i].y);            }        }printf("%.3f\n",sum);    }return 0;}

/*    求最小生成树中的最大边权*/#include <cstdio>#include <algorithm>using namespace std;struct data{int x,y,c;}p[20010];  int n,m,f[2010],x;bool cmp(data a,data b){return a.c<b.c;}int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}int main(){    while(~scanf("%d%d",&n,&m)){        for(int i=1;i<=n;i++)f[i]=i;        for(int i=1;i<=m;i++){            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);        }sort(p+1,p+m+1,cmp);        int ans=0;        for(int i=1;i<=m;i++){            if(sf(p[i].x)!=sf(p[i].y)){                ans=max(ans,p[i].c);                f[sf(p[i].x)]=sf(p[i].y);            }        }printf("%d\n",ans);    }return 0;}