yy1158047452
我像风一样自由~
采纳率35.7%
2020-05-07 00:09 阅读 56

spfa的最短路径问题,告诉我越界不知道错在哪里,求大佬指教

问题:香甜的黄油
时间限制: 1 Sec 内存限制: 128 MB
提交: 117 解决: 50
[提交] [状态] [讨论版] [命题人:admin]
题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的巴甫洛夫,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。

输入
【输入格式】butter.in
第一行: 三个数:奶牛数N,牧场数P(2<=P<=800),牧场间道路数C(1<=C<=1450)。
第二行到第N+1行: 1到N头奶牛所在的牧场号。
第N+2行到第N+C+1行:每行有三个数:相连的牧场A、B,两牧场间距(1<=D<=255),当然,连接是双向的。

输出
一行 输出奶牛必须行走的最小的距离和.

样例输入
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

样例输出
8

提示
样例图形
P1 P2

@--1--@ C1
\ |\
\ | \
5 7 3
\ | \
| \ C3
C2 @--5--@
P3 P4
放在4号牧场最优

#include<bits/stdc++.h>
using namespace std;
bool enter[1000];
//  相连的牧场     两个牧场的距离  每个牧场到某点的距离 
int conn[810][810],w[810][810],dis[810];
int num[810],size[810];//每个牧场的奶牛数   每个牧场有几个与它相连 
int team[1688];//队列 
int main()
{
    int N,P,C;
    while(cin>>N>>P>>C)
    {   
        memset(size,0,sizeof(size)); //将与每点相连数置为0 
        //memset(w,0,sizeof(w));
        //memset(enter,false,sizeof(enter));
        //memset(conn,0,sizeof(conn));
        memset(num,0,sizeof(num));
        for(int i=1;i<=N;i++)
        {
            int x;
            cin>>x;
            num[x]++; 
        }
        for(int i=1;i<=C;i++)
        {
            int x,y,z;
            cin>>x>>y>>z;
            w[x][y]=w[y][x]=z;
            conn[x][++size[x]]=y;//数组模仿连同 
            conn[y][++size[y]]=x;//顺便得到连通个数size 
        }
        int minn;//定义个最小距离 
        minn=0x7fffffff/3;
        for(int k=1;k<=P;k++)
        {
            memset(enter,false,sizeof(enter));
            memset(team,0,sizeof(team));
            for(int i=1;i<=P;i++)
            {
                dis[i]=0x7fffffff;
            }
            int head,tail,u;//定义头尾 和标记头 
            dis[k]=0;team[1]=k;head=0;tail=1;enter[u]=true; 
            do{
                head++;
                head=((head-1)%1601)+1;//为什么这么写呢? 
                u=team[head];
                enter[u]=false;//走到这个了,先出个列 
                for(int j=1;j<=size[u];j++)
                {
                    if(dis[conn[u][j]]>dis[u]+w[u][conn[u][j]])
                    {
                        dis[conn[u][j]]=dis[u]+w[u][conn[u][j]];
                        if(!enter[conn[u][j]])
                        {
                            tail++;
                            tail=((tail-1)%1601)+1;
                            team[tail]=conn[u][j];
                            enter[conn[u][j]]=true;
                        }
                    }
                 } 
            }while(head!=tail);
            int sum=0;//记到该点的总距离 
            for(int i=1;i<=P;i++)
            {
                if(num[i]!=0)
                {
                    sum+=num[i]*dis[i]; 
                }
            }
            minn=min(sum,minn);
        }
        cout<<minn<<endl;
    }
    return 0;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

相关推荐