#include?
#include?
#define?infile?“dquery.in“
#define?outfile?“dquery.out“
#define?maxn?41000
#define?maxlogn?20

struct?anedge{
??????????????long?xydist;
?????????????}e[maxn+1];

struct?edge2{
?????????????long?nodedist;
????????????}*g[maxn+1];

struct?qqnode{
??????????????long?numnow;
?????????????}zhan[maxn+1];

long?degree[maxn+1]distfromroot[maxn+1]level[maxn+1]r[maxn+1]
?????width[maxn+1]done[maxn+1]xl[maxn*2+10]df[maxn*2+10][maxlogn+1]
?????nowtopnmnodexnodey;

FILE?*fin=fopen（infile“r“）
?????*fout=fopen（outfile“w“）;

void?calc_width（）
{
?long?inodeheadtail;
?for?（i=1;?i<=n;?i++）
??done[i]=0;
?head=0;
?tail=1;
?width[1]=1;
?done[1]=1;
?distfromroot[1]=0;
?level[1]=1;
?while?（head??{
???head++;
???node=width[head];
???for?（i=1;?i<=degree[node];?i++）
????if?（done[g[node][i].node]==0）
?????{
??????tail++;
??????width[tail]=g[node][i].node;
??????done[g[node][i].node]=1;
??????distfromroot[width[tail]]=distfromroot[node]+g[node][i].dist;
??????level[width[tail]]=level[node]+1;
?????}
??}
}

void?dfs（）
{
?long?itop;
?top=1;
?zhan[top].num=1;
?zhan[top].now=1;
?done[1]=1;
?while?（top>0）
??{
???nowtop++;
???xl[nowtop]=zhan[top].num;
???while?（（zhan[top].now<=degree[zhan[top].num]）&&（done[g[zhan[top].num][zhan[top].now].node]==1））
????zhan[top].now++;
???if?（zhan[top].now<=degree[zhan[top].num]）
????{
?????done[g[zhan[top].num][zhan[top].now].node]=1;
?????zhan[top+1].num=g[zhan[top].num][zhan[top].now].node;
?????zhan[top+1].now=1;
?????zhan[top].now++;
?????top++;
????}
???while?（（top>=1）&&（zhan[top].now>degree[zhan[top].num]））
????top--;
?}
}

long?min（long?along?b）
{
?if?（level[xl[a]]??return（a）;
??else?return（b）;
}

void?calc_df（）
{
?long?iji2step;
?for?（i=1;?i<=nowtop;?i++）
??df[i][0]=i;
?j=0;
?step=1;
?while?（step<=n）
??{
???j++;
???step*=2;
???for?（i=1;?i<=nowtop;?i++）
????{
?????i2=i+step/2;?//important!!!
?????if?（i2>nowtop）
??????df[i][j]=df[i][j-1];
??????else?df[i][j]=min（df[i][j-1]df[i2][j-1]）;
????}
??}
}

void?init（）
{
?long?ixydist;
?char?c;
?fscanf（fin“%ld%ld“&n&m）;
?for?（i=1;?i<=n;?i++）
??degree[i]=0;
?for?（i=1;?i<=m;?i++）
??{
???fscanf（fin“%ld%ld%ld“&e[i].x&e[i].y&e[i].dist）;
???while?（1）
????{
?????fscanf（fin“%c“&c）;
?????if?（c!=‘?‘）
??????break;
????}
???degree[e[i].x]++;
???degree[e[i].y]++;
??}
?for?（i=1;?i<=n;?i++）
??{
???g[i]=new?（struct?edge2?[degree[i]+2]）;
???g[i][0].node=0;
??}

?for?（i=1;?i<=m;?i++）
??{
???x=e[i].x;
???y=e[i].y;
???dist=e[i].dist;
???g[x][0].node++;
???g[x][g[x][0].node].node=y;
???g[x][g[x][0].node].dist=dist;
???g[y][0].node++;
???g[y][g[y][0].node].node=x;
???g[y][g[y][0].node].dist=dist;
??}

?calc_width（）;

?nowtop=0;
?for?（i=1;?i<=n;?i++）
??done[i]=0;
?dfs（）;
?for?（i=1;?i<=n;?i++）
??r[i]=0;
?for?（i=1;?i<=nowtop;?i++）
??if?（r[xl[i]]==0）
???r[xl[i]]=i;

?calc_

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2002-01-08?07:50??文檔\
?????文件??????275314??2010-10-04?00:00??文檔\NOIP實用算法.pdf
?????目錄???????????0??2002-01-08?07:50??文檔\位運算\
?????目錄???????????0??2002-01-08?07:50??文檔\位運算\位運算簡介及實用技巧\
?????文件???????47104??2008-03-02?23:39??文檔\位運算\位運算簡介及實用技巧\基礎篇.doc
?????文件???????77824??2008-01-27?18:47??文檔\位運算\位運算簡介及實用技巧\實戰篇.doc
?????文件???????60416??2008-01-27?18:46??文檔\位運算\位運算簡介及實用技巧\進階篇.doc
?????目錄???????????0??2002-01-08?07:50??文檔\倍增法\
?????目錄???????????0??2002-01-08?07:50??文檔\倍增法\倍增思想的研究\
?????目錄???????????0??2002-01-08?07:50??文檔\倍增法\倍增思想的研究\problem\
?????目錄???????????0??2002-01-08?07:50??文檔\倍增法\倍增思想的研究\problem\197.files\
?????文件????????7611??2004-01-14?18:02??文檔\倍增法\倍增思想的研究\problem\197.files\p197-01.gif
?????文件????????2101??2004-01-14?18:02??文檔\倍增法\倍增思想的研究\problem\197.files\style-800.css
?????文件????????4147??2004-02-14?11:33??文檔\倍增法\倍增思想的研究\problem\197.htm
?????文件???????24576??2004-04-19?22:38??文檔\倍增法\倍增思想的研究\problem\fmf.doc
?????目錄???????????0??2002-01-08?07:50??文檔\倍增法\倍增思想的研究\problem\Green.files\
?????文件????????4314??2004-02-14?14:13??文檔\倍增法\倍增思想的研究\problem\Green.files\bg4.jpg
?????文件???????36160??2004-02-14?14:13??文檔\倍增法\倍增思想的研究\problem\Green.files\cow1.jpg
?????文件????????9417??2004-02-14?14:23??文檔\倍增法\倍增思想的研究\problem\Green.htm
?????文件?????????640??2004-04-30?09:39??文檔\倍增法\倍增思想的研究\problem\各題說明.txt
?????目錄???????????0??2002-01-08?07:50??文檔\倍增法\倍增思想的研究\program\
?????文件????????2516??2003-02-15?17:37??文檔\倍增法\倍增思想的研究\program\197.CPP
?????文件????????3612??2004-03-20?21:55??文檔\倍增法\倍增思想的研究\program\dquery.cpp
?????文件????????1251??2004-04-19?17:57??文檔\倍增法\倍增思想的研究\program\fib.cpp
?????文件????????5911??2004-03-27?15:08??文檔\倍增法\倍增思想的研究\program\fmf.cpp
?????文件????????1383??2004-04-19?17:41??文檔\倍增法\倍增思想的研究\program\power.cpp
?????文件????????1154??2004-04-19?22:12??文檔\倍增法\倍增思想的研究\program\rmq.cpp
?????文件?????????248??2004-04-19?22:40??文檔\倍增法\倍增思想的研究\program\各程序說明.txt
?????文件??????142336??2004-04-30?09:38??文檔\倍增法\倍增思想的研究\倍增思想的研究.doc
?????文件??????????91??2004-04-16?15:28??文檔\倍增法\倍增思想的研究\說明.txt
?????文件??????168960??2002-09-04?21:28??文檔\分支高精度.ppt
............此處省略1004個文件信息