现在的位置: 首页 > 算法 > 正文

求解释!!!zoj3532 ZOJ Monthly, September 2011

2017年07月15日 算法 ⁄ 共 1894字 ⁄ 字号 评论关闭

此题一直WA,此为WA的代码,哪位神牛级的人物帮我解答一下,在下不胜感激!!!!可怜可怜可怜


#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <map>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int N=1150;
int  inf=1000000000;
map<string ,int >mp;


int p,n,k;
int temp[N];
int num=0;


int  g[N][N];
int dist[N];
bool f[N];




void init()
{
    mp.clear();
    int i,j;
    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
            g[i][j]=inf;
    }
    num=0;
}
void dij(int s)
{
    memset(f,0,sizeof(f));
    fill(dist, dist + num, inf);
    int i,j;
    for(i=0; i<num; i++)
    {
        dist[i]=g[s][i];
    }
    f[s]=1;
    //path[0]=-1;
    for(i=0; i<num-1; i++)
    {
        int  minmum=inf;
        int v;
        for(j=0; j<num; j++)
        {
            if(!f[j]&&dist[j]<minmum)
            {
                minmum=dist[j];
                v=j;
            }
        }
        f[v]=1;
        for(j=0; j<num; j++)
        {
            if(!f[j]&&g[v][j]!=inf&&dist[j]>dist[v]+g[v][j])
            {
                dist[j]=g[v][j]+dist[v];
            }
        }
    }
}


int main()
{
    int case22=1;
    while(scanf("%d%d",&p,&n)!=EOF)
    {


        if(p==0&&n==0)break;
        int i,j,ca;
        init();


        for(ca=0; ca<p; ca++)
        {
            memset(temp,-1,sizeof(temp));
            int to=0;
            scanf("%d ",&k);
            char str[500];
            gets(str);
            int dot=0;
            string ss="";
            for(i=0; i<500&&str[i]!='\0'; i++)
            {
                //cout<<str[i]<<endl;
                if(str[i]==':')
                {
                    if(!mp.count(ss))
                    {
                        mp.insert(pair<string ,int>(ss,num++));
                        temp[to++]=num-1;
                    }
                    else temp[to++]=mp.find(ss)->second;
                    ss="";
                    i++;
                    break;


                }


                if(str[i]==',')
                {
                    if(dot%2==1)
                    {
                        if(!mp.count(ss))
                        {
                            mp.insert(pair<string ,int>(ss,num++));
                            temp[to++]=num-1;
                        }
                        else temp[to++]=mp.find(ss)->second;
                        ss="";
                        i++;
                    }
                    else ss+=str[i];
                    dot++;
                }
                else
                {
                    ss+=str[i];
                }
            }


            for(i=0; i<to; i++)
            {
                for(j=i+1; j<to; j++)
                {
                    g[temp[i]][temp[j]]=min(g[temp[i]][temp[j]],k);
                    g[temp[j]][temp[i]]=min(g[temp[j]][temp[i]],k);
                }
            }
        }
        printf("Database %d\n",case22++);
        for(i=0; i<n; i++)
        {
            char s[50];
            gets(s);
            int tt=mp.find(s)->second;
            if(!mp.count("Kevin, Bacon"))printf("%s: infinity\n",s);
            else {dij(mp.find("Kevin, Bacon")->second);
            if(dist[tt]==inf)printf("%s: infinity\n",s);
            else printf("%s: %d\n",s,dist[tt]);}
        }
        cout<<endl;
    }
    return 0;
}
/*
3 3
3 John, Belushi, Karen, Allen, Kevin, Bacon: Animal House
1 Tom, Hulce, Karen, Allen: Starting Over
1 Hill, Ken, Bob, Stock: kick the ball
John, Belushi
Tom, Hulce
Bob, Stock


*/

抱歉!评论已关闭.