2011-08-16 21:22:44Morris
a141. 變態想要學妹!!!
a141. 柏森想要學妹!!!
內容 ：
從前有一個很會數學又很會寫程式的小小九年級生。
他的名子叫邱柏森。
他很有聰明，但是他瘦巴巴的，看起來就營養不良，而且眼神充滿著交不到女朋友的怨氣。
這種樣子當然是把不到任何很正的學妹呀！(又不是勵志哥)
因此他朋友決定幫助他， 約廷決定用柏森的水壺突破他的異次元，
到那一個屬於他─把的到學妹的世界。
但是中途不知道出了什麼差錯，
異次元一次開太多了(柏森要痛死了)，出現了許多不同的道路(有不同的旅行時間)。
他實在太懶了，因此幫他設計一個程式，能夠馬上告訴他需要多少時間以及其路徑。
因此請你幫幫他，讓他用最快了時間找到他的歸宿。
(本故事純屬虛構，如有雷同，純屬巧合)
輸入說明
：
輸入有N，代表有N筆測資。 每筆測資第一行有N1，N2，代表有N1個點，
N2個邊。 再來有N2行的a b w 代表是從a到b或從b到a所需要的時間是w。
再來有一個N3代表接下來有幾筆詢問。 再來有N3行s和t，分別是起始點和終點。
輸出說明
：
輸出時要先標示第幾筆Case(從輸入算起)
再來輸出a->b還有所需要最少的時間
還有Path(也就是路徑)
記的要在最後印出"GO!! MICHAEL!!Wish you can get your girlfriend!!!"(不含引號)
最多會有100個節點，以及很多很多的邊。
範例輸入 ：
1 7 10 1 2 32 1 6 3 2 6 7 2 3 21 2 5 12 3 5 6 3 7 11 5 4 13 4 7 9 3 6 2 5 2 4 2 7 3 4 1 4 3 1
範例輸出 ：
Case#1: 2->4:25 Path:2->5->4 Case#2: 2->7:20 Path:2->6->3->7 Case#3: 3->4:19 Path:3->5->4 Case#4: 1->4:24 Path:1->6->3->5->4 Case#5: 3->1:5 Path:3->6->1 GO!! MICHAEL!!Wish you can get your girlfriend!!!
提示
：
背景知識：
最短路問題
要誠心誠意的希望柏森把的到學妹才能AC喔!!!!
謝謝"no306100"的糾正與指教:)(做個朋友吧)
AC的大大可不可以幫小的生更難的測資，
還請多多回函，並請附上程式碼。
3Q。
出處
：
/**********************************************************************************/
/* Problem: a141 "柏森想要學妹!!!" from 上課數學課的胡思亂想 */
/* Language: C */
/* Result: AC (4ms, 246KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-16 16:37:18 */
/**********************************************************************************/
#include<stdio.h>
#define MaxV 1000000
void MergeSort(int, int);
void Merge(int, int, int);
struct Link {
short x, y, w;
}Data[1001], X[1001];
int NodeT[1001], NodeL[1001];
void Print_Path(int now, int L[], int flag) {
if(L[now] != -1) Print_Path(L[now], L, 0);
printf("%d%s", now, flag == 0 ? "->": "\n");
}
int SPFA(int st, int ed, int N) {
int a, b, c, D[N+1], L[N+1], tn, Queue[100000], Qt = 0;
char Used[N+1];
for(a = 0; a <= N; a++)
D[a] = MaxV, Used[a] = 0;
Queue[0] = st, D[st] = 0, L[st] = -1;
if(st == 0) D[ed] = 0, L[ed] = st;
for(a = 0; a <= Qt; a++) {
tn = Queue[a], Used[tn] = 0;
for(b = 0, c = NodeL[tn]; b < NodeT[tn]; b++, c++) {
if(Data[c].w + D[tn] < D[Data[c].y]) {
D[Data[c].y] = Data[c].w + D[tn], L[Data[c].y] = tn;
if(Used[Data[c].y] == 0)
Used[Data[c].y] = 1, Queue[++Qt] = Data[c].y;
}
}
}
printf("%d->%d:%d\nPath:", st, ed,D[ed]);
Print_Path(ed, L, 1);
return 0;
}
main() {
int t, n, m, x, y, w, a, C = 0, Q;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(a = 0; a <= n; a++)/*init*/
NodeT[a] = 0, NodeL[a] = MaxV;
for(a = 0; a < m; a++) {
scanf("%d %d %d", &x, &y, &w);
Data[a].x = x, Data[a].y = y, Data[a].w = w;
Data[a+m].x = y, Data[a+m].y = x, Data[a+m].w = w;
NodeT[x]++, NodeT[y]++;
}
MergeSort(0, 2*m-1);
for(a = 0; a < 2*m; a++)
NodeL[Data[a].x] = NodeL[Data[a].x] < a ? NodeL[Data[a].x]: a;
scanf("%d", &Q);
while(Q--) {
scanf("%d %d", &x, &y);
printf("Case#%d:\n", ++C);
SPFA(x, y, n);
}
}
puts("GO!! MICHAEL!!Wish you can get your girlfriend!!!");
return 0;
}
void MergeSort(int l, int h) {
if(l < h) {
int m = (l+h)/2;
MergeSort(l, m);
MergeSort(m+1, h);
Merge(l, m, h);
}
}
void Merge(int l, int m, int h) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h) {
if(Data[In1].x < Data[In2].x || (Data[In1].x == Data[In2].x && Data[In1].w <= Data[In2].w))
X[Top++] = Data[In1++];
else
X[Top++] = Data[In2++];
}
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= h) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
上一篇：a160. 變態想要下棋!!!
下一篇：d906. 2. 排座位問題