hdoj1598

明天好好理解一下这段代码。。写的一知半解。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define maxn 210
#define maxe 2010
#define inf 1000000000
using namespace std;
typedef struct Edge{
    int w;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int pre[maxn];
int outque[maxn];
bool inque[maxn];
int n,m;
bool spfa(int low,int high,int s,int t)
{
    int i;
    queue<int> q;
    memset(outque,0,sizeof(outque));
    memset(inque,0,sizeof(inque));
    for(i=1;i<=n;i++)
        dist[i]=inf;
    dist[s]=0;
    inque[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        inque[u]=0;
        outque[u]++;
        if(outque[u]>n-1) return false;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            int w=edge[i].w;
            if(w<low || w>high)
                continue;
            if(dist[v]>dist[u]+edge[i].w)
            {
                dist[v]=dist[u]+edge[i].w;
                if(v==t)
                    return true;
                if(!inque[v])
                {
                    q.push(v);
                    inque[v]=1;
                }
            }
        }
    }
    return false;
}

int main()
{
    int i,j;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        int a,b;
        int cnt=0;
        int max=-1;
        int w[maxe];
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&a,&b,&w[i]);
            if(max<w[i])
                max=w[i];
            edge[cnt].w=w[i];
            edge[cnt].to=b;
            edge[cnt].next=head[a];
            head[a]=cnt++;

            edge[cnt].w=w[i];
            edge[cnt].to=a;
            edge[cnt].next=head[b];
            head[b]=cnt++;
        }
        int query;
        sort(w+1,w+1+m);
        scanf("%d",&query);
        for(i=1;i<=query;i++)
        {
            int start,end;
            scanf("%d %d",&start,&end);
            if(!spfa(0,max,start,end))
            {
                printf("-1\n");
                continue;

            }

            int l=0,r=max+1,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                bool flag=0;
                for(j=1;w[j]<=max-mid;j++)
                {
                    if(spfa(w[j],w[j]+mid,start,end))
                    {
                        flag=1;
                        break;
                    }

                }
                if(flag)
                {
                    r=mid;
                }
                else
                    l=mid+1;
            }
            printf("%d\n",l);



        }


    }
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>