本文共 2366 字，大约阅读时间需要 7 分钟。

#include
   
    using namespace std;const int maxn=10017;const int maxm=200007;const int inf = 99999999;struct node{
       int to;    int next;    int cost;}edge[maxm];struct node2{
       int id;    int mis;    double av;}ans[maxn];bool cmp(node2 q,node2 w){
       if(q.av==w.av&&q.mis==w.mis) return q.id
    
     w.mis;}int cnt,head[maxn];int dis[17][maxn];int vis[maxn];void add(int x,int y,int z){
       edge[++cnt].to=y;    edge[cnt].next=head[x];    edge[cnt].cost=z;    head[x]=cnt;    edge[++cnt].to=x;    edge[cnt].next=head[y];    edge[cnt].cost=z;    head[y]=cnt;}int n,m,k,d;int trans(string s){
       int len=s.length();    int num=0;    for(int i=1;i
     
      dis[cur-n][cur]+edge[i].cost)        dis[cur-n][v]=dis[cur-n][cur]+edge[i].cost;    }    vis[cur]=1;    for(int i=1;i<=n+m;i++)    {
           int mi=inf,flag;        for(int j=1;j<=n+m;j++){
           //printf("cur:%d to:%d dis:%d\n",cur,j,dis[cur][j]);        if(dis[cur-n][j]
      
       dis[cur-n][flag]+edge[j].cost)            dis[cur-n][v]=dis[cur-n][flag]+edge[j].cost;        }    }}int main(){
       string a,b;    int l,x,y;    scanf("%d%d%d%d",&n,&m,&k,&d);    memset(dis,0x3f,sizeof(dis));    while(k--)    {
           cin>>a>>b>>l;        if(a[0]=='G') x=trans(a);        else x=trans2(a);        if(b[0]=='G') y=trans(b);        else y=trans2(b);        add(x,y,l);    }   /* for(int i=1;i<=n+m;i++)    {        for(int j=head[i];j;j=edge[j].next)        {            printf("from:%d to:%d cost:%d\n",i,edge[j].to,edge[j].cost);        }    }*/    int ct=0;    for(int i=n+1;i<=n+m;i++)    {
           int flag=0,mi=inf,sum=0;        memset(vis,0,sizeof(vis));        dij(i);        for(int j=1;j<=n;j++)        {
              // printf("i:%d j:%d dis:%d\n",i,j,dis[i][j]);            if(dis[i-n][j]>d)            {
                   flag=1;                break;            }            mi=min(mi,dis[i-n][j]);            sum+=dis[i-n][j];        }        if(flag==1) continue;        ans[++ct].av=(double)sum/n;        ans[ct].id=i-n;        ans[ct].mis=mi;    }    sort(ans+1,ans+1+ct,cmp);    //for(int i=1;i<=m;i++)    //printf("%d %d %.2lf\n",ans[i].id,ans[i].mis,ans[i].av);    if(ct==0)    {
           printf("No Solution\n");    }    else    {
           printf("G%d\n",ans[1].id);        printf("%d.0 %.1lf\n",ans[1].mis,ans[1].av);    }    return 0;}
      
     
    
   

转载地址：http://osgwi.baihongyu.com/