簡(jiǎn)單計(jì)算題（二）課件

第三講簡(jiǎn)單計(jì)算題（二）ACM算法與程序設(shè)計(jì)數(shù)學(xué)科學(xué)學(xué)院：汪小平wxiaoping325@163.com第三講簡(jiǎn)單計(jì)算題（二）ACM算法與程序設(shè)計(jì)數(shù)學(xué)科學(xué)學(xué)院：汪CDOJ_1365木桿上的螞蟻/problem.php?pid=1365Description

在一根細(xì)木桿上，有一些速度相同螞蟻，它們有的往左走，有的往右走，木桿很細(xì)，只允許一只螞蟻通過(guò)，所以當(dāng)兩只螞蟻碰頭的時(shí)候，它們會(huì)掉頭繼續(xù)前進(jìn)，直到走出邊界，掉下木桿。

已知木桿的長(zhǎng)度和每只螞蟻的名字、位置和初始方向，問(wèn)依次掉下木桿的螞蟻花費(fèi)的時(shí)間以及它的名字。CDOJ_1365木桿上的螞蟻DescriptionInput輸入包含多組測(cè)試數(shù)據(jù)。第一行包含一個(gè)整數(shù)T(T<=20)，代表測(cè)試數(shù)據(jù)組數(shù)。每組測(cè)試數(shù)據(jù)的第一行包含兩個(gè)整數(shù)NL，表示有N只螞蟻(N<=100)，木桿長(zhǎng)度為L(zhǎng)(L<=1000)。假設(shè)螞蟻每秒前進(jìn)一個(gè)單位距離，掉頭轉(zhuǎn)向的時(shí)間忽略不計(jì)。以下N行，每行依次為螞蟻的名字（長(zhǎng)度不超過(guò)10，僅由英文字母組成），初始位置p（0<p<L，整數(shù)，表示螞蟻離木桿最左端的距離），初始方向（一個(gè)字符，L表示向左，R表示向右），以單個(gè)空格分隔，數(shù)據(jù)保證初始不會(huì)有兩只螞蟻在同一個(gè)位置。InputOutput對(duì)于第k組測(cè)試數(shù)據(jù)，首先輸出一行為“Case#k:”。然后輸出N行，給出依次掉下木桿的螞蟻花費(fèi)的時(shí)間以及它的名字，以單個(gè)空格分隔。（按照掉下木桿的先后順序輸出，數(shù)據(jù)保證不會(huì)有兩支螞蟻同時(shí)掉下木桿）。SampleInput2

25

GG1L

MM3R

25

GG1R

MM2LSampleOutputCase#1:

1GG

2MM

Case#2:

2GG

4MMOutputSampleOutput#include<cstdio>#include<algorithm>//因?yàn)橐胹ort算法#defineN100usingnamespacestd;//必須引用名字空間stdstructant_type{intpos;charname[11];}ants[N];structevent_type{intdrop_time;chardir;}events[N];boolcmp_ant(constant_type&p,constant_type&q){returnp.pos<q.pos;}#include<cstdio>boolcmp_event(constevent_type&p,constevent_type&q){returnp.drop_time<q.drop_time;}intmain(){chardir[2];inti,k,n,L,R,T;scanf("%d",&T);for(k=1;k<=T;k++){scanf("%d%d",&n,&L);for(i=0;i<n;i++){scanf("%s%d%s",ants[i].name,&ants[i].pos,dir);events[i].dir=dir[0];events[i].drop_time=(dir[0]=='L'?ants[i].pos:L-ants[i].pos);}boolcmp_event(constevent_typsort(ants,ants+n,cmp_ant);sort(events,events+n,cmp_event);printf("Case#%d:\n",k);L=0;R=n-1;for(i=0;i<n;i++){if(events[i].dir=='L'){printf("%d%s\n",events[i].drop_time,ants[L].name);L++;}else{printf("%d%s\n",events[i].drop_time,ants[R].name);R--;}}}return0;}sort(ants,ants+n,c往屆校賽題目精選CDOJ_10048球勝負(fù)(eight)

/problem.php?pid=1004往屆校賽題目精選CDOJ_10048球勝負(fù)(eigDescription8球是一種臺(tái)球競(jìng)賽的規(guī)則。臺(tái)面上有7個(gè)紅球、7個(gè)黃球以及一個(gè)黑球，當(dāng)然還有一個(gè)白球。對(duì)于本題，我們使用如下的簡(jiǎn)化規(guī)則：紅、黃兩名選手輪流用白球擊打各自顏色的球，如果將該顏色的7個(gè)球全部打進(jìn)，則這名選手可以打黑球，如果打進(jìn)則算他勝。如果在打進(jìn)自己顏色的所有球之前就把黑球打進(jìn)，則算輸。如果選手不慎打進(jìn)了對(duì)手的球，入球依然有效?，F(xiàn)在給出打進(jìn)的球（白球除外）的順序，以及黑球由哪方打進(jìn)，你的任務(wù)是判定哪方是勝者。

假設(shè)不會(huì)有一桿同時(shí)打進(jìn)一顆黑球和其他彩球。DescriptionInput

輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)第一行是一個(gè)整數(shù)N(1<=N<=15)，表示打進(jìn)的球的個(gè)數(shù)，N=0表示結(jié)束。隨后有一行，包含N個(gè)字符，依序表示打進(jìn)的是何種球。如果是’B’，表示是紅方打進(jìn)的黑球，如果是’L’，表示是黃方打進(jìn)的黑球。如果是’Y’則表示是黃球，’R’表示紅球。字符間沒(méi)有空格。所有輸入都滿(mǎn)足如下條件：最后一顆球打進(jìn)時(shí)這局比賽正好結(jié)束，而且打進(jìn)的紅球和黑球都不超過(guò)7個(gè)。Output

對(duì)每組數(shù)據(jù)，輸出一行。如果紅方勝，輸出’Red’；黃方勝，輸出’Yellow’。InputSampleInput5

RYRRB

9

RRRRYRRRB

0SampleOutputYellow

RedSampleInput2008年校賽最簡(jiǎn)單的題目。只需要判斷最后一個(gè)球是誰(shuí)打進(jìn)的，然后統(tǒng)計(jì)這個(gè)人自己的球是不是已經(jīng)全部打進(jìn)了，就可以得到答案。2008年校賽最簡(jiǎn)單的題目。#include<cstdio>#include<cstring>intmain(){charstr[30];inti,n,cnt,k;boolflag;while(1){scanf("%d",&n);if(n==0)break;scanf("%s",str);k=strlen(str)-1;//最后一個(gè)球下標(biāo)if(str[k]=='B')//最后一個(gè)球是紅方打進(jìn)的黑球{cnt=0;for(i=0;i<k;i++)if(str[i]=='R')cnt++;//統(tǒng)計(jì)黑球之前進(jìn)了幾個(gè)紅球if(cnt==7)flag=true;//進(jìn)了7個(gè)紅球則紅方勝elseflag=false;//否則黃方勝}#include<cstdio>else//最后一個(gè)球是黃方打進(jìn)的黑球{cnt=0;for(i=0;i<k;i++)if(str[i]=='Y')cnt++;//統(tǒng)計(jì)黑球之前進(jìn)了幾個(gè)黃球if(cnt==7)flag=false;//進(jìn)了7個(gè)紅球則黃方勝elseflag=true;//否則紅方勝}if(flag)printf("Red\n");elseprintf("Yellow\n");}return0;}else//最后一個(gè)球是黃方打進(jìn)的黑球CDOJ_1005點(diǎn)球大戰(zhàn)(penalty)

/problem.php?pid=1005CDOJ_1005點(diǎn)球大戰(zhàn)(penalty)

httDescription

在足球比賽中，有不少賽事，例如世界杯淘汰賽和歐洲冠軍聯(lián)賽淘汰賽中，當(dāng)比賽雙方經(jīng)過(guò)正規(guī)比賽和加時(shí)賽之后仍然不分勝負(fù)時(shí)，需要進(jìn)行點(diǎn)球大戰(zhàn)來(lái)決定誰(shuí)能夠獲得最終的勝利。點(diǎn)球大戰(zhàn)的規(guī)則非常簡(jiǎn)單，兩方輪流派出球員罰點(diǎn)球，每方各罰5個(gè)。當(dāng)5輪點(diǎn)球結(jié)束以后如果仍然不分勝負(fù)，則進(jìn)入一輪定勝負(fù)的階段。兩方各派一名球員罰點(diǎn)球，直到有一方罰進(jìn)而另一方?jīng)]有進(jìn)為止。在北美職業(yè)冰球聯(lián)賽中，也有點(diǎn)球大戰(zhàn)。與足球的規(guī)則不同的是，它只先罰3輪點(diǎn)球，隨后就進(jìn)入一輪定勝負(fù)的階段，而其他的規(guī)則完全一樣。在本題中，輸入將給出每次點(diǎn)球是否罰進(jìn)，而你的任務(wù)則是輸出一個(gè)“比分板”。DescriptionInput

輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行包含一個(gè)整數(shù)N(1<=N<=18)，表示雙方總共罰了多少個(gè)點(diǎn)球，N=0表示輸入結(jié)束。隨后有N行，每行是一個(gè)如下形式的字符串：XXXXgood：表示這個(gè)點(diǎn)球罰進(jìn)或者XXXXnogood：表示這個(gè)點(diǎn)球沒(méi)有罰進(jìn)其中XXXX表示球員名字（全部由字母和空格組成，保證不會(huì)出現(xiàn)歧義）每一行保證不超過(guò)100個(gè)字符。XXXX和good以及XXXX和no、no和good之間保證有且只有1個(gè)空格。

good、nogood都是小寫(xiě)。本題是大小寫(xiě)相關(guān)的。數(shù)據(jù)不保證點(diǎn)球大戰(zhàn)一定結(jié)束，也不保證在結(jié)束以后立即結(jié)束這組數(shù)據(jù)（即：不用判斷點(diǎn)球大戰(zhàn)是否結(jié)束，只用把罰進(jìn)的點(diǎn)球往比分上加即可）。Output對(duì)每組數(shù)據(jù)，輸出一個(gè)比分板。一個(gè)點(diǎn)球如果罰進(jìn)，則在對(duì)應(yīng)的地方標(biāo)上’O’，如果沒(méi)有進(jìn)則標(biāo)上’X’。先罰球的隊(duì)伍的信息在上面，后罰的在下面。最右邊標(biāo)上兩隊(duì)的比分。具體格式參考樣例輸出。注意如果一輪點(diǎn)球只罰了一個(gè)，則后面那個(gè)點(diǎn)球?qū)?yīng)的地方寫(xiě)上’-’。InputSampleInput6

Riisegood

Ballackgood

Gerrardnogood

Lampardnogood

FernandoTorresgood

Maloudagood

9

ChristianoRonaldonogood

Messinogood

Giggsgood

Abidalnogood

Carrickgood

Ronaldinhogood

Rooneygood

Henrynogood

Tevezgood

0SampleOutput123Score

OXO2

OXO2

12345Score

XOOOO4

XXOX-1SampleInput名字可以包含空格，甚至可以包含no、good（事實(shí)上，大部分?jǐn)?shù)據(jù)都包含no和good中的至少一個(gè)），所以此題比較好的處理方法是找跳過(guò)名字，直接找倒數(shù)第二個(gè)單詞，看它是不是no，是就是沒(méi)踢進(jìn)，反之就是踢進(jìn)；數(shù)據(jù)可能很詭異，比如有兩種特殊情況，一種是只有一個(gè)good，另一種是直接nogood。這兩組數(shù)據(jù)不是太滿(mǎn)足題意（第一組名字為空，第二組有歧義）空格數(shù)要和樣例輸出一樣，否則很可能會(huì)被判為“格式錯(cuò)誤”(PresentationError)。名字可以包含空格，甚至可以包含no、good（事實(shí)上，大部分#include<cstdio>#include<cstring>booljudge(char*str){intpos=strlen(str)-1;while(str[pos]!='')pos--;//從一行字符串的最后開(kāi)始向前尋找第一個(gè)空格str[pos]='\0';pos--;while(str[pos]!='')pos--;//繼續(xù)向前尋找第二個(gè)空格if(strcmp(str+pos+1,"no")==0)return0;return1;}參考源代碼#include<cstdio>參考源代碼intmain(){inti,j,n;while(1){scanf("%d",&n);//掃描雙方罰點(diǎn)球的人數(shù)if(n==0)break;intboard[15][2]={0};//至多15個(gè)回合，每回合兩隊(duì)各罰一次charstr[110];gets(str);str[0]='';for(i=0;i<n;i++){gets(str+1);//掃描一行罰點(diǎn)球信息if(judge(str))//判斷是否踢進(jìn)點(diǎn)球board[i/2][i%2]=1;//1或2表示踢進(jìn)，否則為0elseboard[i/2][i%2]=2;}參考源代碼intmain()參考源代碼intcnt[2]={0};//存放兩隊(duì)點(diǎn)球比分for(i=0;i<(n+1)/2;i++)printf("%d",i+1);//輸出點(diǎn)球進(jìn)行的回合數(shù)量，之間空格隔開(kāi)printf("Score\n");for(i=0;i<2;i++){for(j=0;j<(n+1)/2;j++){if(board[j][i]==1){printf("O");cnt[i]++;}elseif(board[j][i]==2)printf("X");elseprintf("-");}printf("%d\n",cnt[i]);}}return0;}intcnt[2]={0};//存放兩隊(duì)點(diǎn)CDOJ_1048Clock

/problem.php?pid=1048Description

ClockisinventedbyancientArabicengineersandwhichcontributestobuildtheconceptofaccuratetimeforushumanbeingsandevencouldbeessentialtoolthatwidelyusedinindustry,businessandourroutinelives.Nevertheless,theideologyofclockturnsouttobequitesimplythatevenmakesensetolittlekids.WecouldhardlyimaginethathowdoArabicwisdomcomeupwithsuchideatoindicatetimeonlybytwoorthreefingers.CDOJ_1048Clock

http://acmTheotherday,hhbareaskinglxhandHysramptoplayhisnewlyinventedgamedescribeasfollow.hhbrandomlychangethetimeofhislovelyalarmclockthenasklxhandHysramptotellthedegreebetweenhourfingerandminutefinger.lxhseemsquitegiftedplayingitwhileHysrampdoesnot.WhenHysrampfailstoanswerhhb,hhbsmilestoHysramp.AndHysrampsmilestoyou,anaceprogrammer.Theotherday,hhbareaskiInput

ThefirstlineoftheinputcontainsoneintegerT,whichindicatethenumberoftestcases.Eachtestcasecontainsoneindicatingthetimeonhhb’sclockintheformofHH:MM.(0<=HH<24,0<=MM<60)Output

Onelineforeachtestcasecontainsonlyonenumberindicatingtheanswer.Anintegeroranirreduciblefractionindicatedthedegreebetweenhourfingerandminutefinger.InputSampleInput1

00:00SampleOutput0SampleInput怎么才能計(jì)算出時(shí)針和分針之間的夾角?直接算注意：1、答案是整數(shù)或不可約分?jǐn)?shù)2、答案在[0,180]之間怎么才能計(jì)算出時(shí)針和分針之間的夾角?#include<stdio.h>intmain(){ intt,p,hh,mm,sh,sm,res; scanf("%d",&t); for(p=1;p<=t;p++) { scanf("%d:%d",&hh,&mm); if(hh>=12) hh=hh-12; sh=hh*60+mm; sm=mm*12; if(sh>sm)res=sh-sm; elseres=sm-sh; if(res>=360)res=720-res; if(res%2==0)printf("%d\n",res/2); elseprintf("%d/2\n",res); } return0;}#include<stdio.h>CDOJ_1049Flagstone

/problem.php?pid=1049Description

IntheQingshuiheCampusofUESTC,themostannoyproblemtostudentsaretheflagstonepathonthelawn.Thedesignerseemssostupidthattheflagstonepathoftenmakestudentsstepinthegap.Nowaperfectstepiswantedinordertonotstepinanygapsandsteponeveryflagstone.Thesteplengthisrequiredtobeconstantwhilethelengthoftheflagstoneandgaparegivendifferent.Theproblemisaskingyoutotelltheminimumlengthoftheperfectstep.Tosimplifythequestion,thefootisconsideredtobeapointandtheverybeginningistheforeedgeofthefirstflagstone,whichalsomeansthefirstflagstonehasalreadybeensteppedon.CDOJ_1049Flagstone

http://acInputThefirstlineoftheinputcontainsoneintegerT,whichindicatethenumberoftestcases.Ineachtestcase,thefirstlinecontainsanintegerN(2<=N<=1e5),indicatingthenumberofflagstone.FollowingNlines,andeachlineisthelengthofoneflagstone.AndthefollowingN-1linesarethelengthofthegaps.Alldataisinteger.Allthelengthwillbeapositiveinteger,andthesumofthemwillfitina32bitsignedinteger.OutputOnelineforeachtestcasecontainsonlyonenumberindicatingtheanswer.Onerealnumberindicatingtheperfectsteplengthshouldbeaccuratetotwodigitsaftertheradixpoint.Ifitisimpossibletofindoutaperfectstep,justoutput

“impossible”!InputSampleInput22

10

20

5

3

10

20

5

5

1000SampleOutput15.00

impossibleSampleInput每個(gè)石板踏且僅踏一次對(duì)于第i塊石板，一定是踏了i-1步到達(dá)的。設(shè)第i塊石板的左邊界和右邊界離起點(diǎn)的距離分別為L(zhǎng)和R，可以確定步長(zhǎng)必須在區(qū)間[L/(i-1),R/(i-1)]之內(nèi)。問(wèn)題轉(zhuǎn)化為求多個(gè)區(qū)間的交。如果交集為空，則答案為impossible，否則輸出交區(qū)間的左界。每個(gè)石板踏且僅踏一次#include<stdio.h>inta[100001];intb[100001];intmain(){ intt,p; intn,i; doubleh,l; doublehh,ll; doubles; scanf("%d",&t); for(p=1;p<=t;p++) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<n;i++) scanf("%d",&b[i]);#include<stdio.h> s=0; l=a[1]+b[1]; h=a[1]+b[1]+a[2]; for(i=1;i<n;i++) { s=s+a[i]+b[i]; ll=s/(double)i; hh=(s+a[i+1])/(double)i; if(ll>l)l=ll; if(hh<h)h=hh; } if(l<=h)printf("%.2lf\n",l); elseprintf("impossible\n"); } return0;} s=0;CDOJ_1043輸出前m大的數(shù)據(jù)

/problem.php?pid=1043ProblemDescription給你n個(gè)整數(shù)，請(qǐng)按從大到小的順序輸出其中前m大的數(shù)。Input每組測(cè)試數(shù)據(jù)有兩行，第一行有兩個(gè)數(shù)n,m(0<n,m<1000000)，第二行包含n個(gè)各不相同，且都處于區(qū)間[-500000,500000]的整數(shù)。Output對(duì)每組測(cè)試數(shù)據(jù)按從大到小的順序輸出前m大的數(shù)。

CDOJ_1043輸出前m大的數(shù)據(jù)

http://acSampleinput:533-3592213-644Sampleoutput:213923Sampleinput:常規(guī)的思想是？常規(guī)的結(jié)果是？數(shù)據(jù)的特點(diǎn)是？加速的方法是？如果數(shù)據(jù)可以重復(fù)呢？用最好的排序TLE各不相同HASH處理沖突常規(guī)的思想是？用最好的排序#include<stdio.h>#include<string.h>#defineN1000000inta[N];intmain(void){inti,j,n,m,t;while(scanf("%d%d",&n,&m)==2){memset(a,0,N*sizeof(int));for(i=0;i<n;i++){scanf("%d",&t);a[t+N/2]++;//下標(biāo)對(duì)應(yīng)數(shù)+N/2，元素值存儲(chǔ)重復(fù)次數(shù)}for(t=0,i=N-1;t<m&&i>=0;){if(a[i]>0)//對(duì)應(yīng)有數(shù){printf("%d",i-N/2);//打印對(duì)應(yīng)的數(shù)t++;//計(jì)數(shù)器增加if(--a[i]==0)i--;}elsei--;}printf("\n");}return0;}#include<stdio.h>CDOJ_1010最短路

/problem.php?pid=1010Description在每年的校賽里，所有進(jìn)入決賽的同學(xué)都會(huì)獲得一件很漂亮的T-shirt。但是每當(dāng)我們的工作人員把上百件的衣服從商店運(yùn)回到賽場(chǎng)的時(shí)候，卻是非常累的！所以現(xiàn)在他們想要尋找最短的從商店到賽場(chǎng)的路線(xiàn)，你可以幫助他們嗎？CDOJ_1010最短路

http://acm.uesInput輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)第一行是兩個(gè)整數(shù)N、M（N<=100，M<=10000），N表示成都的大街上有幾個(gè)路口，標(biāo)號(hào)為1的路口是商店所在地，標(biāo)號(hào)為N的路口是賽場(chǎng)所在地，M則表示在成都有幾條路。N=M=0表示輸入結(jié)束。接下來(lái)M行，每行包括3個(gè)整數(shù)A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路，我們的工作人員需要C分鐘的時(shí)間走過(guò)這條路。

輸入保證至少存在1條商店到賽場(chǎng)的路線(xiàn)。

Output對(duì)于每組輸入，輸出一行，表示工作人員從商店走到賽場(chǎng)的最短時(shí)間InputSampleInput

21

123

33

125

235

312

00

SampleOutput3

2SampleInputDijkstra算法Dijkstra算法能求一個(gè)頂點(diǎn)到另一頂點(diǎn)最短路徑。它是由Dijkstra于1959年提出的。實(shí)際它能出始點(diǎn)到其它所有頂點(diǎn)的最短路徑。Dijkstra算法是一種標(biāo)號(hào)法：給賦權(quán)圖的每一個(gè)頂點(diǎn)記一個(gè)數(shù)，稱(chēng)為頂點(diǎn)的標(biāo)號(hào)（臨時(shí)標(biāo)號(hào)，稱(chēng)T標(biāo)號(hào)，或者固定標(biāo)號(hào)，稱(chēng)為P標(biāo)號(hào)）。T標(biāo)號(hào)表示從始頂點(diǎn)到該標(biāo)點(diǎn)的最短路長(zhǎng)的上界；P標(biāo)號(hào)則是從始頂點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)。Dijkstra算法步驟如下：Dijkstra算法Dijkstra算法能求一個(gè)頂點(diǎn)Dijkstra算法Dijkstra算法2816715129342963117924v1v2v3v4v5v6v7v8v9v10v118132---固定編號(hào)，下標(biāo)表示前趨頂點(diǎn)---臨時(shí)編號(hào)，下標(biāo)表示前趨頂點(diǎn)2816715129342963117924v1v2v3v42816715129342963117924v1v2v3v4v5v6v7v8v9v10v110∞∞∞∞∞∞∞218111v42816715129342963117924v1v2v3v5v6v7v8v9v10v110∞∞104∞∞∞∞2181112816715129342963117924v1v2v3v421v2v42816715129342963117924v1v3v5v6v7v8v9v10v11032∞104∞∞∞∞8111v521v2v42816715129342963117924v1v3v6v7v8v9v10v11065104∞12555∞81113221v2v42816715129342963117924v1v8v521v2v42816715129342963117924v1v3v6v7v9v10v11065104∞12514881115532v6v8v521v2v42816715129342963117924v1v3v7v9v10v110104∞1251487611553265v8v521v2v428167151293429631179v3v6v8v521v2v42816715129342963117924v1v7v9v10v11093∞1251481155326576v7v3v6v8v521v2v42816715129342963117924v1v9v10v110107125148115532657693v3v6v8v521v2v42816715129342963v10107v7v3v6v8v521v2v42816715129342963117924v1v9v1101110148115532657693v91110v10107v7v3v6v8v521v2v42816715129342963117924v1v110139115532657693v10107v7v3v6v8v521v2v428167151v11v91110v10107v7v3v6v8v521v2v42816715129342963117924v10115532657693139312v11v91110v10107v7v3v6v8v521v2v42816715129429631794v10115532657693139v11v91110v10107v7v3v6v8v521v2v312v11v91110v10107v7v3v6v8v521v2v42111221v10115532657693139解最短路問(wèn)題的基本方法--Dijkstra算法把以頂點(diǎn)及其前趨頂點(diǎn)作為端點(diǎn)的邊作為一個(gè)集合，該邊集導(dǎo)出的子圖是一個(gè)生成樹(shù)。該生成樹(shù)是否是最小生成樹(shù)？312v11v91110v10107v7v3v6v8v521#include<iostream>usingnamespacestd;intmap[110][110];//存放鄰接矩陣#defineINF10000000//表示無(wú)窮intmain(){intn,m;while(1){scanf("%d%d",&n,&m);if(n==0&&m==0)break;