3104 問題 O: 信息學(xué)奧賽一本通T1345-香甜的黃油
時間限制: 1s
內(nèi)存限制: 128MB 提交: 23 解決: 13
題目描述
農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法:糖。把糖放在一片牧場上,他知道N(1≤N≤500)只奶牛會過來舔它,這樣就能做出能賣好價錢的超甜黃油。當(dāng)然,他將付出額外的費用在奶牛上。
農(nóng)夫John很狡猾。像以前的巴甫洛夫,他知道他可以訓(xùn)練這些奶牛,讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲,以至他可以在晚上擠奶。
農(nóng)夫John知道每只奶牛都在各自喜歡的牧場(一個牧場不一定只有一頭牛)。給出各頭牛在的牧場和牧場間的路線,找出使所有牛到達(dá)的路程和最短的牧場(他將把糖放在那)。
輸入
第一行: 三個數(shù):奶牛數(shù)N,牧場數(shù)P(2≤P≤800),牧場間道路數(shù)C(1≤C≤1450)。
第二行到第N+1行: 1到N頭奶牛所在的牧場號。
第N+2行到第N+C+1行:每行有三個數(shù):相連的牧場A、B,兩牧場間距(1≤D≤255),當(dāng)然,連接是雙向的。
樣例輸入
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
提示
說明:放在4號牧場最優(yōu)。