#include <iostream>
#include <cstdlib>
#include <memory>
using namespace std;
const int maxn=40001;
struct dist_type
{
    int pre,val;
}dist[maxn];
int q[maxn],al[maxn][4],len[maxn][4],ans[maxn][2];
bool e[maxn];
void build_tree(int root)
{
           int head,tail,temp,i,j;
           head=tail=0;q[0]=root;
           e[root]=1;
           do
           {
                temp=tail;
                for(i=head;i<=temp;i++)
                {
                    for(j=0;j<4;j++)
                        if(!al[q[i]][j])break;
                        else
                        if(!e[al[q[i]][j]])
                        {
                           dist[al[q[i]][j]].pre=q[i];
                           tail++;
                           q[tail]=al[q[i]][j];
                           e[al[q[i]][j]]=1;
                        }
                }
                head=temp+1;        
           }while(tail>=head);
}
int main(int argc, char *argv[])
{
    int i,j,x,y,head,tail,temp,sum,max,n,m;
    char c;
    while(cin>>n>>m)
    {
          memset(dist,0,sizeof(dist));
          memset(e,0,sizeof(e));
          memset(ans,0,sizeof(ans));
          memset(al,0,sizeof(al));
          for(i=0;i<m;i++)
          {
              fin>>x>>y>>sum>>c;
              for(j=0;j<4;j++)
                  if(!al[x][j])
                  {
                     al[x][j]=y;
                     len[x][j]=sum;
                     break;
                  }
              for(j=0;j<4;j++)
                  if(!al[y][j])
                  {
                     al[y][j]=x;
                     len[y][j]=sum;
                     break;
                  }
           }
           for(i=1;i<=n;i++)
               if(!dist[i].pre)
                  build_tree(i);
           head=0;tail=-1;
           for(i=1;i<=n;i++)
               if(dist[i].pre)
                  e[dist[i].pre]=0;
           for(i=1;i<=n;i++)
           {
               if(e[i])
               {
                  tail++;q[tail]=i;
               }
           }
           do
           {
                temp=tail;
                for(i=head;i<=temp;i++)
                {
                    if(!dist[q[i]].pre)continue;
                    if(!e[dist[q[i]].pre])
                    {
                       tail++;q[tail]=dist[q[i]].pre;
                       e[q[tail]]=1;
                    }
                    for(j=0;j<4;j++)
                        if(al[q[i]][j]==dist[q[i]].pre)
                           break;
                    if(len[q[i]][j]+dist[q[i]].val>dist[dist[q[i]].pre].val)
                       dist[dist[q[i]].pre].val=len[q[i]][j]+dist[q[i]].val;
                    if(len[q[i]][j]+dist[q[i]].val>ans[dist[q[i]].pre][0])
                    {
                       ans[dist[q[i]].pre][1]=ans[dist[q[i]].pre][0];                 
                       ans[dist[q[i]].pre][0]=len[q[i]][j]+dist[q[i]].val;
                    }
                    else
                    if(len[q[i]][j]+dist[q[i]].val>ans[dist[q[i]].pre][1])
                       ans[dist[q[i]].pre][1]=len[q[i]][j]+dist[q[i]].val;
                }
                head=temp+1;        
           }while(tail>=head);
           max=0;
           for(i=1;i<=n;i++)
               if(ans[i][0]+ans[i][1]>max)
                  max=ans[i][0]+ans[i][1];
           cout<<max<<endl;
    }
    //system("PAUSE");	
    return 0;
}

• 二次BFS可以解决吧 (3746) achilles 2004-11-06 14:57:56