簡(jiǎn)單計(jì)算題二

第三講

簡(jiǎn)單計(jì)算題（二）ACM算法與程序設(shè)計(jì)2023/5/152關(guān)于本次比賽電子科技大學(xué)第十三屆程序設(shè)計(jì)競(jìng)賽暨西南地區(qū)高校邀請(qǐng)賽參賽選手來(lái)自電子科技大學(xué)在讀學(xué)生（包括本科生、碩士和博士）決賽會(huì)邀請(qǐng)來(lái)自西南地區(qū)高校的ACM-ICPC專業(yè)隊(duì)伍參加，但不參與校內(nèi)評(píng)獎(jiǎng)2023/5/153關(guān)于本次比賽報(bào)名報(bào)名時(shí)間：3月27日晚9點(diǎn)截止。

務(wù)必保證填寫(xiě)的個(gè)人信息真實(shí)，被拒絕參賽的隊(duì)伍可能是因?yàn)樘顚?xiě)信息有誤或不完整。通過(guò)審核的隊(duì)伍用注冊(cè)的帳號(hào)和密碼登錄CDOJ參加比賽。若有任何疑問(wèn)/尋求組隊(duì)可以在的此次競(jìng)賽專區(qū)發(fā)貼。2023/5/154關(guān)于本次比賽初賽時(shí)間：3月28號(hào)星期六上午9：00～晚上9：00初賽采用網(wǎng)絡(luò)賽形式，地址初賽排名約前50左右的隊(duì)伍有機(jī)會(huì)晉級(jí)決賽The13thUESTCProgrammingContestWarmup1 2012-03-2109:00:00~21:00:00The13thUESTCProgrammingContestWarmup2 2012-03-2616:20:00~21:20:00初賽期間，我們給使用電腦不方便的同學(xué)開(kāi)放科研2號(hào)樓208作為比賽機(jī)房。初賽后公布所有選手代碼，供交流和學(xué)習(xí)。嚴(yán)查作弊，組委會(huì)判定代碼雷同的選手將取消其成績(jī)。2023/5/155關(guān)于本次比賽決賽時(shí)間：4月4日星期四13：00–18：00地點(diǎn)：清水河校區(qū)科A227、229決賽會(huì)邀請(qǐng)來(lái)自西南地區(qū)高校的ACM/ICPC專業(yè)隊(duì)伍參加。外校隊(duì)伍不參與校內(nèi)評(píng)獎(jiǎng)2023/5/156關(guān)于本次比賽獎(jiǎng)項(xiàng)設(shè)置

1.晉級(jí)決賽的同學(xué)將獲得紀(jì)念T-shirt 2.獲獎(jiǎng)隊(duì)員發(fā)給證書(shū)，作為學(xué)校評(píng)定獎(jiǎng)學(xué)金加分與創(chuàng)新學(xué)分的依據(jù)。

3.比賽成績(jī)會(huì)作為校ACM-ICPC隊(duì)員選拔的重要依據(jù)

4.表現(xiàn)突出的選手，將有機(jī)會(huì)代表電子科技大學(xué)參加2015年四川省大學(xué)生程序設(shè)計(jì)競(jìng)賽。

校賽后請(qǐng)各位報(bào)名參加比賽的同學(xué)將你們的比賽賬號(hào)和隊(duì)員姓名在課堂上進(jìn)行登記；根據(jù)初賽和決賽所完成的題目數(shù)量進(jìn)行打分，分?jǐn)?shù)成績(jī)將作為各位同學(xué)中期測(cè)試成績(jī)，約占期末總成績(jī)的20%，希望大家都能努力拼一把！校賽往年題目精選CDOJ_10048球勝負(fù)(eight)

Description8球是一種臺(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)一顆黑球和其他彩球。Input

輸入包含多組數(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)有空格。

所有輸入都滿足如下條件：最后一顆球打進(jìn)時(shí)這局比賽正好結(jié)束，而且打進(jìn)的紅球和黑球都不超過(guò)7個(gè)。Output

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

RYRRB

9

RRRRYRRRB

0SampleOutputYellow

Red2008年校賽最簡(jiǎn)單的題目。只需要判斷最后一個(gè)球是誰(shuí)打進(jìn)的，然后統(tǒng)計(jì)這個(gè)人自己的球是不是已經(jīng)全部打進(jìn)了，就可以得到答案。#include<stdio.h>#include<string.h>intmain(){intn;while(1){scanf("%d",&n);if(n==0)break;charstr[30];scanf("%s",str);intl=strlen(str)-1;//統(tǒng)計(jì)打進(jìn)球的數(shù)量

boolflag;if(str[l]=='B')//判斷最后一個(gè)球是不是紅方打進(jìn)的黑球

{intrc=0;for(intct0=0;ct0<l;ct0++)if(str[ct0]=='R')rc++;//統(tǒng)計(jì)黑球之前進(jìn)了幾個(gè)紅球

if(rc==7)flag=1;//進(jìn)了7個(gè)紅球則紅方勝elseflag=0;//否則黃方勝

}else//最后一個(gè)球是黃方打進(jìn)的黑球

{intrc=0;for(intct0=0;ct0<l;ct0++)if(str[ct0]=='Y')rc++;//統(tǒng)計(jì)黑球之前進(jìn)了幾個(gè)黃球

if(rc==7)flag=0;//進(jìn)了7個(gè)紅球則黃方勝

elseflag=1;//否則紅方勝

}if(flag)printf("Red\n");elseprintf("Yellow\n");}return0;}CDOJ_1005點(diǎn)球大戰(zhàn)(penalty)

Description

在足球比賽中，有不少賽事，例如世界杯淘汰賽和歐洲冠軍聯(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è)“比分板”。Input

輸入包含多組數(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ě)上’-’。SampleInput6

Riisegood

Ballackgood

Gerrardnogood

Lampardnogood

FernandoTorresgood

Maloudagood

9

ChristianoRonaldonogood

Messinogood

Giggsgood

Abidalnogood

Carrickgood

Ronaldinhogood

Rooneygood

Henrynogood

Tevezgood

0SampleOutput123Score

OXO2

OXO2

12345Score

XOOOO4

XXOX-1名字可以包含空格，甚至可以包含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ù)不是太滿足題意（第一組名字為空，第二組有歧義）空格數(shù)要和樣例輸出一樣，否則很可能會(huì)被判為“格式錯(cuò)誤”(PresentationError)。#include<iostream>booljudge(char*str){intl=strlen(str);intpos=l-1;while(str[pos]!='')pos--;//從一行字符串的最后開(kāi)始向前尋找第一個(gè)空格

str[pos]='\0';intnpos=pos-1;while(str[npos]!='')npos--;//繼續(xù)向前尋找第二個(gè)空格

if(strcmp(str+npos+1,"no")==0)return0;//比較從npos+1所指向的空格后的第一個(gè)字符開(kāi)始到

//“\0”之間的字符串是否等同“no”return1;}參考源代碼intmain(){intn;while(1){scanf("%d",&n);if(n==0)break;intgg[15][2]={0};//至多15個(gè)回合，每回合兩隊(duì)各罰一次

charstr[110];gets(str);//掃描雙方罰點(diǎn)球的人數(shù)

for(intct0=0;ct0<n;ct0++){gets(str);//掃描一行罰點(diǎn)球信息

if(judge(str))//判斷是否踢進(jìn)點(diǎn)球

gg[ct0/2][ct0%2]=1;//1或2表示踢進(jìn)，否則為0elsegg[ct0/2][ct0%2]=2;}intcct[2]={0};//存放兩隊(duì)點(diǎn)球比分

for(intct0=0;ct0<(n+1)/2;ct0++)printf("%d",ct0+1);//輸出點(diǎn)球進(jìn)行的回合數(shù)量，之間空格隔開(kāi)printf("Score\n");for(intct0=0;ct0<2;ct0++){for(intct1=0;ct1<(n+1)/2;ct1++){if(gg[ct1][ct0]==1){printf("O");cct[ct0]++;}elseif(gg[ct1][ct0]==2)printf("X");elseprintf("-");}printf("%d\n",cct[ct0]);}}return0;}CDOJ_1048Clock

Description

ClockisinventedbyancientArabicengineersandwhichcontributestobuildtheconceptofaccuratetimeforushumanbeingsandevencouldbeessentialtoolthatwidelyusedinindustry,businessandourroutinelives.Nevertheless,theideologyofclockturnsouttobequitesimplythatevenmakesensetolittlekids.WecouldhardlyimaginethathowdoArabicwisdomcomeupwithsuchideatoindicatetimeonlybytwoorthreefingers.Theotherday,hhbareaskinglxhandHysramptoplayhisnewlyinventedgamedescribeasfollow.hhbrandomlychangethetimeofhislovelyalarmclockthenasklxhandHysramptotellthedegreebetweenhourfingerandminutefinger.lxhseemsquitegiftedplayingitwhileHysrampdoesnot.WhenHysrampfailstoanswerhhb,hhbsmilestoHysramp.AndHysrampsmilestoyou,anaceprogrammer.Input

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

Onelineforeachtestcasecontainsonlyonenumberindicatingtheanswer.Anintegeroranirreduciblefractionindicatedthedegreebetweenhourfingerandminutefinger.SampleInput1

00:00SampleOutput0怎么才能計(jì)算出時(shí)針和分針之間的夾角?直接算注意：1、答案是整數(shù)或不可約分?jǐn)?shù)2、答案在[0,180]之間#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;}CDOJ_1049Flagstone

DescriptionIntheQingshuiheCampusofUESTC,themostannoyproblemtostudentsaretheflagstonepathonthelawn.Thedesignerseemssostupidthattheflagstonepathoftenmakestudentsstepinthegap.Nowaperfectstepiswantedinordertonotstepinanygapsandsteponeveryflagstone.Thesteplengthisrequiredtobeconstantwhilethelengthoftheflagstoneandgaparegivendifferent.Theproblemisaskingyoutotelltheminimumlengthoftheperfectstep.Tosimplifythequestion,thefootisconsideredtobeapointandtheverybeginningistheforeedgeofthefirstflagstone,whichalsomeansthefirstflagstonehasalreadybeensteppedon.InputThefirstlineoftheinputcontainsoneintegerT,whichindicatethenumberoftestcases.Ineachtestcase,thefirstlinecontainsanintegerN(2<=N<=1e5),indicatingthenumberofflagstone.FollowingNlines,andeachlineisthelengthofoneflagstone.AndthefollowingN-1linesarethelengthofthegaps.Alldataisinteger.Allthelengthwillbeapositiveinteger,andthesumofthemwillfitina32bitsignedinteger.OutputOnelineforeachtestcasecontainsonlyonenumberindicatingtheanswer.Onerealnumberindicatingtheperfectsteplengthshouldbeaccuratetotwodigitsaftertheradixpoint.Ifitisimpossibletofindoutaperfectstep,justoutput

“impossible”!SampleInput22

10

20

5

3

10

20

5

5

1000SampleOutput15.00

impossible每個(gè)石板踏且僅踏一次對(duì)于第i塊石板，一定是踏了i-1步到達(dá)的。設(shè)第i塊石板的左界和右界離起點(diǎn)的距離L,R，可以確定步長(zhǎng)必須在區(qū)間[L/(i-1),R/(i-1)]之內(nèi)。問(wèn)題轉(zhuǎn)化為求多個(gè)區(qū)間的交。如果交集為空，則答案為impossible，否則輸出交區(qū)間的左界。#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]);//n塊石板 for(i=1;i<n;i++) scanf(“%d”,&b[i]);//n-1個(gè)間隔 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;//第i塊步長(zhǎng)左區(qū)間 hh=(s+a[i+1])/(double)i;//第i塊右區(qū)間 if(ll>l)l=ll; if(hh<h)h=hh;//計(jì)算步長(zhǎng)區(qū)間的交集 } if(l<=h)printf(“%.2lf\n”,l);//交集存在 elseprintf("impossible\n"); } return0;}這些題目都是近幾年的初賽題目，大家覺(jué)得難度如何？太簡(jiǎn)單了?。?！對(duì)于我們公選課的那20%的期中測(cè)試成績(jī)還有什么好擔(dān)心的。希望在下周一的網(wǎng)絡(luò)賽場(chǎng)上見(jiàn)到教室中的每一位同學(xué)CDOJ_1043輸出前m大的數(shù)據(jù)

ProblemDescription

給你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ù)。

Sampleinput:533-3592213-644Sampleoutput:213923HDOJ_1425

sort

常規(guī)的思想是？常規(guī)的結(jié)果是？數(shù)據(jù)的特點(diǎn)是？加速的方法是？如果數(shù)據(jù)可以重復(fù)呢？用最好的排序TLE各不相同HASH處理沖突#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;}Hash表簡(jiǎn)介——基本原理

哈希表（散列表）的基本原理： 使用一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素，一般通過(guò)設(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)，即散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對(duì)應(yīng)，然后用該數(shù)組單元來(lái)存儲(chǔ)對(duì)應(yīng)元素。Hash表簡(jiǎn)介——函數(shù)構(gòu)造無(wú)定式，方法很多最常見(jiàn)的方法：除余法 H(k)=kmodp

(p一般選取適當(dāng)大的素?cái)?shù))常用的經(jīng)典字符串Hash后面介紹Hash表簡(jiǎn)介——沖突由于不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此很有可能出現(xiàn)如下情況：“對(duì)于不同的元素關(guān)鍵字，Hash函數(shù)計(jì)算出了相同的函數(shù)值”，這就是產(chǎn)生了所謂的“沖突”。換句話說(shuō)，就是Hash函數(shù)把不同的元素分在了相同的下標(biāo)單元。Hash表簡(jiǎn)介——沖突解決 方法很多～ 常用方法：線性探測(cè)再散列技術(shù) 即：當(dāng)h(k)位置已經(jīng)存儲(chǔ)有元素的時(shí)候，依次探查(h(k)+i)modS,i=1,2,3…，直到找到空的存儲(chǔ)單元為止。其中，S為數(shù)組長(zhǎng)度。 特別地，如果將數(shù)組掃描一圈仍未發(fā)現(xiàn)空單元，則說(shuō)明哈希表已滿，這會(huì)帶來(lái)麻煩，但是，該情況完全可以通過(guò)擴(kuò)大數(shù)組范圍來(lái)避免。Hash表簡(jiǎn)介——基本操作Hash表初始化（0或-1或其它）哈希函數(shù)運(yùn)算插入元素（包含沖突解決）定位（需考慮可能沖突的情況）總結(jié)：Hash函數(shù)評(píng)價(jià)標(biāo)準(zhǔn)：低沖突率易于編碼Hash函數(shù)特點(diǎn)：優(yōu)點(diǎn)：數(shù)據(jù)存儲(chǔ)和查找效率高 （幾乎是常數(shù)時(shí)間）缺點(diǎn)：消耗較多內(nèi)存（內(nèi)存很便宜哪～）Hash主要應(yīng)用：查找元素是否屬于集合搜索中的狀態(tài)表示

整數(shù)Hash

例1(HDOJ-1496Equations)Considerequationshavingthefollowingform:a*x12+b*x22+c*x32+d*x42=0

a,b,c,dareintegersfromtheinterval[-50,50]andanyofthemcannotbe0.Itisconsiderasolutionasystem(x1,x2,x3,x4)thatverifiestheequation,xiisanintegerfrom[-100,100]andxi!=0,anyi∈{1,2,3,4}.Determinehowmanysolutionssatisfythegivenequation.HDOJ-1496題目分析題意簡(jiǎn)單（類似“百錢(qián)買(mǎi)百雞”問(wèn)題）傳統(tǒng)方法是（幾重循環(huán)）？復(fù)雜度？上述方法如何判斷兩端相等？（查找？）可行方案（兩重循環(huán)＋Hash存儲(chǔ)查找）Hash表大小？HDOJ-1496參考代碼（1）//bylinle#include"stdio.h"#include"memory.h"intpin[101];inthash[2000003];intmain(){inta,b,c,d;inti,j,sum;for(i=1;i<101;i++)pin[i]=i*i;while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){……}}if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){printf("0\n");continue;}memset(hash,0,sizeof(hash));for(i=1;i<=100;i++)for(j=1;j<=100;j++)hash[a*pin[i]+b*pin[j]+1000000]++;sum=0;for(i=1;i<=100;i++)for(j=1;j<=100;j++)sum+=hash[-(c*pin[i]+d*pin[j])+1000000];printf("%d\n",sum*16);CDOJ_1010最短路

Description

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

輸入包括多組數(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)的路線。

Output

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

21

123

33

125

235

312

00

SampleOutput3

2#include<iostream>usingnamespacestd;intmap[110][110];//存放鄰接矩陣#defineINF10000000//表示無(wú)窮intmain(){intn,m;while(1){scanf("%d%d",&n,&m);if(n==0&&m==0)break;for(intct0=0;ct0<110;ct0++){for(intct1=0;ct1<110;ct1++){map[ct0][ct1]=INF;}}