Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Keeps WA... 谁有数据？

Posted by shit at 2004-11-06 11:45:56 on Problem 1985
In Reply To:无向图，用GCC不会溢出 Posted by:xiaomi at 2004-11-05 23:34:03
```#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)
{
e[root]=1;
do
{
temp=tail;
{
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;
}
}
}
int main(int argc, char *argv[])
{
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);
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;
{
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;
}
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;
}```

Followed by: