View Code of Problem 631

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 101




int graph[N][N];
int i,j;
int cost[N];//the time you cost
int pre[N];//record your father point
int vis[N];//record whether the point is visited


typedef struct my_queue
{
    int maxsize;
    int head,tail;
    int num[100];
}my_queue;

int judge_empty(my_queue *q)
{
    if(q->head==q->tail)
        return 1;
    else return 0;
}

int judge_full(my_queue *q)
{
    if(q->head==(q->tail+1)%q->maxsize)
        return 1;
    else
        return 0;
}

int get_head(my_queue *q)
{
    return q->num[q->head];
}

int my_pop(my_queue *q)
{
    if(judge_empty(q))
        return 0;
    q->head=(q->head+1)%q->maxsize;
    return 1;
}

int my_push(my_queue *q,int n)
{
    if(judge_full(q))
        return 0;
    q->num[q->tail]=n;
    q->tail=(q->tail+1)%q->maxsize;
    return 1;
}

int _switch(char str[][5])
{//string to integer
    if(strcmp(*str,"x")==0)
        return 10000;
    int sum=0;
    char *p=*str;
    while(*p)
    {
        sum=sum*10+(*p)-'0';
        p++;
    }
    return sum;
}

void create(int n)
{// create the graph
    int sum;
    char tmp[5];
    for(i=1;i<=n;i++)
    {
        for(j=1;j<i;j++)
        {
            scanf("%s",tmp);
            sum=_switch(&tmp);
            graph[i][j]=graph[j][i]=sum;
        }
    }
}



int spfa_bfs(int s,int n)
{//s is the start point
    int counter[n];//记录顶点入队次数，若入队次数大于顶点数，说明存在负权环
    my_queue q;
    q.maxsize=100;
    q.head=q.tail=0;
    memset(counter,0,sizeof(counter));
    memset(cost,0x3f,sizeof(cost));
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
    cost[s]=0;
    my_push(&q,s);
    vis[s]=1;
    counter[s]++;
    while(!judge_empty(&q))
    {
        int tmp=get_head(&q);
        my_pop(&q);
        vis[tmp]=0;
        //队首元素出队Ř
        for(i=1;i<=n;i++)
        {
            if(i==tmp) continue;
            int len=graph[tmp][i];
            if(len<10000)
            {//遍历与队首元素相连的点
                if(cost[tmp]+len<cost[i])
                {//如果能更新起点到该点的值，就更新该值
                    cost[i]=cost[tmp]+len;
                    if(!vis[i])
                    {//若能更新，且该点未进入队列，就将其入队
                        my_push(&q,i);
                        vis[i]=1;
                        counter[i]++;
                        if(counter[i]>n)//如果该点入队次数超过顶点数n，说明该图存在负权环，直接推出
                            return 0;
                    }
                }
            }
        }
    }
     return 1;
}



int main()
{
    int n,tmp=0;
    scanf("%d",&n);
    create(n);
    spfa_bfs(1,n);
    //spfa_dfs(1);
    for(i=1;i<=n;i++)
    {
        if(tmp<cost[i]&&cost[i]<10000)
            tmp=cost[i];
    }
    printf("%d\n",tmp);
    return 0;
}