【POJ 1125】Stockbroker Grapevine

http://acm.nyist.net/JudgeOnline/talking.php?pid=426&page=2

数据增大非常多 用到非常多东西才干过 (弱没过，。。

这题就是求最短路寻找全部通路中最大权的最小值外加考验英语水平……

Floyd 208K 0MS 1162B

#includeusing namespace std;int dis[111][111],n;void Floyd()
{
    int i,j,k,tmax,mmax,f;    for(k = 1; k <= n; ++k)
        for(i = 1; i <= n; ++i)
            for(j = 1; j <= n; ++j)
                if(dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
    mmax = INF;    for(i = 1; i <= n; ++i)
    {
        f = 1;
        tmax = 0;
        for(j = 1; j <= n; ++j)
        {
            if(i == j) continue;
            if(dis[i][j] == INF) f = 0;
            tmax = max(tmax,dis[i][j]);
        }
        if(f && tmax < mmax)
        {
            k = i;
            mmax = tmax;
        }
    }
    if(mmax != INF) printf("%d %d\n",k,mmax);
    else puts("disjoint");
}int main()
{
    int i,k,v;
    while(~scanf("%d",&n) && n)
    {
        memset(dis,INF,sizeof(dis));
        for(i = 1; i <= n; ++i)
        {
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d",&v);
                scanf("%d",&dis[i][v]);
            }
        }
        Floyd();
    }    return 0;
}

Dijkstra 168K 0MS 1491B

#includeusing namespace std;typedef struct Edge
{
    int v,w,next;
}Edge;Edge eg[11111];
int head[111],dis[111],n,tp;
bool vis[111];int Dijkstra(int u)
{
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[u] = 0;    int m,p,i,j;    for(i = 1; i <= n; ++i)
    {
        p = -1;
        m = INF;
        for(j = 1; j <= n; ++j)
        {
            if(!vis[j] && dis[j] < m)
            {
                p = j;
                m = dis[j];
            }
        }
        if(i == n || p == -1) break;
        vis[p] = 1;        for(j = head[p]; j != -1; j = eg[j].next)
        {
            if(!vis[eg[j].v] && dis[eg[j].v] > dis[p] + eg[j].w)
                dis[eg[j].v] = dis[p] + eg[j].w;
        }    }
    if(p == -1) return INF;
    return dis[p];
}int main()
{
    int i,k,m,t;
    while(~scanf("%d",&n) && n)
    {
        m = INF;
        tp = 0;
        memset(head,-1,sizeof(head));
        for(i = 1; i <= n; ++i)
        {
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d %d",&eg[tp].v,&eg[tp].w);
                eg[tp].next = head[i];
                head[i] = tp++;
            }
        }
        k = 0;
        for(i = 1; i <= n; ++i)
        {
            t = Dijkstra(i);
            if(t < m)
            {
                k = i;
                m = t;
            }
        }
        if(k)
            printf("%d %d\n",k,m);
        else puts("disjoint");
    }    return 0;
}

SPFA 180K 0MS 1668B

#includeusing namespace std;typedef struct Edge
{
    int v,w,next;
}Edge;Edge eg[11111];
int head[111],dis[111],n,tp;
bool vis[111];int SPFA(int u)
{
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[u] = 0;
    queue <int> q;
    q.push(u);
    int v,w,i,p,m;    while(!q.empty())
    {
        p = q.front();
        q.pop();
        vis[u] = 0;
        for(i = head[p]; i != -1; i = eg[i].next)
        {
            v = eg[i].v;
            w = eg[i].w;
            if(dis[v] > dis[p] + w)
            {
                dis[v] = dis[p] + w;
                if(!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    m = 0;
    for(i = 1; i <= n; ++i)
    {
        if(i == u) continue;
        if(dis[i] == INF) return INF;
        m = max(m,dis[i]);
    }
    return m;
}int main()
{
    int i,k,m,t;
    while(~scanf("%d",&n) && n)
    {
        m = INF;
        tp = 0;
        memset(head,-1,sizeof(head));
        for(i = 1; i <= n; ++i)
        {
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d %d",&eg[tp].v,&eg[tp].w);
                eg[tp].next = head[i];
                head[i] = tp++;
            }
        }
        k = 0;
        for(i = 1; i <= n; ++i)
        {
            t = SPFA(i);
            if(t < m)
            {
                k = i;
                m = t;
            }
        }
        if(k)
            printf("%d %d\n",k,m);
        else puts("disjoint");
    }    return 0;
}