15.problems全國(guó)青少年信息學(xué)奧林匹克

1、青少年信息學(xué)中國(guó)國(guó)家隊(duì)訓(xùn)練 2010-2011宋方競(jìng)賽時(shí)間：待定題目R 星際旅可執(zhí)行文輸入文標(biāo)準(zhǔn)輸標(biāo)準(zhǔn)標(biāo)準(zhǔn)輸出文標(biāo)準(zhǔn)輸標(biāo)準(zhǔn)標(biāo)準(zhǔn)每個(gè)測(cè)試2 1 1 測(cè)試點(diǎn)每個(gè)測(cè)試5是否有部否是否題目傳統(tǒng)提交源程序須加PascalC 對(duì)于C語(yǔ)注意：最終測(cè)試時(shí)，所有編譯命令均不打開(kāi)任何優(yōu)化開(kāi)關(guān)。R 集【問(wèn)題描述】星際探【問(wèn)題描述】眾所周知，新世紀(jì)的科學(xué)很發(fā)達(dá)，于是Ry和Ren開(kāi)始了星際探險(xiǎn)，他們?cè)谟钪嬷虚_(kāi)辟了一片空間，建造了N個(gè)空間站。這N個(gè)空間站由一些單向的時(shí)空隧道連接，這些時(shí)空隧道都有一個(gè)穿越指數(shù)，穿過(guò)這些時(shí)空隧道，你可以走到未來(lái)或者回到過(guò)去，當(dāng)然，這些都是由穿越指數(shù)決定的。有一天，Ray和Ren開(kāi)始了一場(chǎng)比賽

2、。他們要從一個(gè)空間站S出發(fā)去另一個(gè)空間站T，先到的人獲勝。Raen 一定會(huì)選一條能最快到達(dá)T的路線。他希望Ry 輸給他，所以事先在Ray 的飛船上設(shè)定了飛行路徑，使得 Ry 從S 到T只能走一條特定的路徑。但是，Ray 有對(duì)策，他有一臺(tái)能夠 時(shí)空隧道的機(jī)器，這臺(tái)機(jī)器每次可以把某一條時(shí)空隧道的穿越指數(shù)增加或減少1，但是因?yàn)闄C(jī)器很累，所以ay 希望盡可能少改動(dòng)，當(dāng)然，如果改動(dòng)后從某個(gè)空間站經(jīng)過(guò)一系列的穿越可以在從這個(gè)空間站出發(fā)之前回到這個(gè)空間站，那么這樣的改動(dòng)是不允許的。修改之后，Ren依然會(huì)走能最快到達(dá)終點(diǎn)的路線，所以Ry 是不可能贏的。但他請(qǐng)你幫助他確定改動(dòng)時(shí)空隧道的方案，使得他能和Ren 同

3、時(shí)到達(dá)T?！据斎敫袷健縉 M ，代表空間站的數(shù)目和時(shí)空隧道M uv wu vw0 = w = 2000?？臻g站的是 0 N 1。M + 2 pRaven Ray p = NM + 3 p 個(gè)互不相同的數(shù)，表示那條路徑上的空間站的編號(hào)，第一個(gè)數(shù)是 S，最后一個(gè)數(shù)是 T ?！据敵龈袷健康那闆r下時(shí)間機(jī)器的最小次數(shù)。Miwi條時(shí)空隧道的穿越指數(shù)增加 w， w 可以是負(fù)數(shù)。如果第一問(wèn)（時(shí)間機(jī)器的最小次數(shù)）正確，可以得到該測(cè)試20% 的分?jǐn)?shù)，如果在此基礎(chǔ)上方案可行，能得到該測(cè)試點(diǎn) 100% 的分【樣例輸入】3 0 1 1 2 0 【樣例輸出】【數(shù)據(jù)范圍】一共個(gè)數(shù)據(jù)，對(duì)于第i (1 = i = 10) 個(gè)數(shù)據(jù)，N = iMi5000旅【問(wèn)題描述】Ray 樂(lè)旅游，這次他來(lái)到了T 城。T 城是一個(gè)水上城市，一共【樣例輸入】30 1 1 2 8SUM 0 MAX 0 N 0 SUM 0 MIN0C 1 SUM 0 MAX 0 【樣例輸出