濰坊昌邑一中提高1班圖題目

1、1. 第二最短路徑(second)已知一個(gè)圖，求其中兩點(diǎn)的第二最短路徑長度。輸入格式：第一行：n，m，x，y（n 頂點(diǎn)數(shù)30，m100 邊數(shù)，x 起點(diǎn)，y終點(diǎn)）；以下 m 行，每行三個(gè)整數(shù)：i，j，k(0。輸出格式：X 和y 之間的第二最短路徑長度。樣例輸入：57121272346151樣例輸出：42. 最小花費(fèi)(money)問題描述在n 個(gè)人中，某些人的之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬續(xù)費(fèi)各不相同。給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾續(xù)費(fèi)，請問 A 最少需要使得轉(zhuǎn)賬后 B 收到 100 元。輸入格式：第一行：兩個(gè)用空格隔開的正整數(shù) n,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對數(shù)。

2、以下 m 行：每行輸入三個(gè)用空格隔開的正整數(shù) x,y,z，表示標(biāo)號為x 的人和標(biāo)號為 y 的人之間互相轉(zhuǎn)賬需要扣除 z%續(xù)費(fèi)(0z100)。最后一行：兩個(gè)用空格隔開的正整數(shù) A,B。數(shù)據(jù)保證 A 與 B 之間可以直接或間接地轉(zhuǎn)賬。輸出格式：輸出 A 使得 B 到賬 100 元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后 3位。輸入樣例3 31 2 12 3 21 3 31 3輸出樣例103.072數(shù)據(jù)范圍對于 30%的數(shù)據(jù)，滿足 1=n=100對于所有數(shù)據(jù)，滿足 1=n 2 - 3 - 4 - 7總時(shí)間為 10 + 12 + 20 + 8 = 50，的情況是3-4 那一段，要多花 20 秒（因?yàn)樾凶咚俣葴p

3、半），所以這條路選需要 70 秒二：1 - 2 - 5 - 6 - 4 - 7總時(shí)間為 10 + 10 + 12 + 13 + 8 = 53，的情況是 6-4 那一段，要多花 13 秒（因?yàn)樾凶咚俣葴p半），所以這條路選需要 66 秒三：1 - 7總時(shí)間為 34 = 34，的情況是 1-7 那一段，要多花 34 秒（因pyramid.inpyramid.out7 81 2 102 3 123 4 204 7 81 7 342 5 105 6 126 4 1366需要 68 秒為行走速度減半），所以這條路選4.觀光路線(trip)問題描述島的 Adelton 城鎮(zhèn)上有一個(gè)旅游機(jī)構(gòu)。他們決定在提在供

4、許多的其他吸引之外，再向客人們提供旅游本鎮(zhèn)的服務(wù)。為了從提供的吸引服務(wù)中盡可能地獲利，這個(gè)旅游機(jī)構(gòu)接受了一個(gè)精明決定：在相同的起點(diǎn)和終點(diǎn)之間找出一條最短路線。你的任務(wù)是編寫一個(gè)程序來找這樣的一條路線。在這個(gè)鎮(zhèn)上，有N 個(gè)1 至 N），兩個(gè)路口（路口之間可以有多條道路連接，有 M 條道路（為 1 至M）。但沒有一條道路從一個(gè)路口出發(fā)又回到同一個(gè)路口。每一條觀光線路都是由一些路組成的，這些道路序號是：y_1,y_k，且 k2。第 y_i（1=i=k-1）是連接第 x_i路口和第x_i+1號路口的；其中第 y_k 號路是連接第x_k號路口和第 x_1 號路口。而且所有的這些 x_1,x_k 分別代號表不同路口的序號。在某一條觀光線所有道路的長度的和就是這條觀光線路的總長度。換言之 L(y_1)+L(y_2)+L(y_k)的和就是該條光線路的長度。你的程序必須計(jì)算出觀光線路的最小長度，或者說這個(gè)城鎮(zhèn)上不存在這樣的觀光線路。輸入格式：第一行路口的個(gè)數(shù) N(N=100)；道路的數(shù)目 M（M10000）。接下來的每一行描述一條路，每一行有三個(gè)正整數(shù)：這條路連接，以及這條路的長度(小于 500 的正整數(shù))。的兩個(gè)路口的輸出格式：如果觀光路線不存在的話就輸出”No solution”，否則輸出觀光路線的最小長度。