2011-10-29 07:31:11Morris
a280. 小朋友上樓梯
a280. 小朋友上樓梯
內容 ：
有一個小朋友，站在第 0 階樓梯上，他想要到第 n 階去。
厲害的是，這個樓梯的每一階都有自動傳送功能，
小朋友只需要選擇他想要到哪一階去，閉上眼再睜開，就到那裡去了！
例如：
第 0 階可以傳送到第 4 和第 7 階；
第 4 階會傳送到第 9 階；
第 7 階會傳送到第 3 階和第 8 階；
第 3 階會傳送到第 5 階。
那麼，小朋友如果要到第 5 階，他就可以藉由 0 -> 7 -> 3 -> 5 的傳送來到達。
現在請告訴他，是否存在那麼一種傳送法可以讓他到達目的地呢？
輸入說明
：
輸入的第一行有兩個數字 n 和 k ( 0 < n <= 100 )，其中 k ( k<=10000 ) 表示這個神奇樓梯總共有幾種傳送管道。
接下來會有 k 行，每行有兩個數字 a 和 b ( 0 <= a, b <= 100 )，表示第 a 階樓梯可以傳送到第 b 階樓梯。
輸出說明
：
如果可以，請輸出「Ok!」，否則請輸出「Impossib1e!」。
範例輸入 ：
5 6 0 4 0 7 4 9 7 3 7 8 3 5 5 6 0 4 0 7 4 9 7 0 7 8 3 5
範例輸出 ：
Ok! Impossib1e!
提示
：
出處
：
用單源路徑 or BFS 即可
/**********************************************************************************/
/* Problem: a280 "小朋友上樓梯" from */
/* Language: C (1407 Bytes) */
/* Result: AC(64ms, 616KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 20:42:36 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 100000
typedef struct {
int x, y, v;
}Pair;
Pair Path[10001];
int cmp(const void *i, const void *j) {
Pair *x, *y;
x = (Pair *)i, y = (Pair *)j;
if(x->x < y->x) return -1;
else if(x->x == y->x)
return x->v - y->v;
else return 1;
}
int Min(int x, int y) {
return x < y ? x : y;
}
int NodeT[101], NodeL[101], Q[10001];
int SPFA(int st, int ed, int N) {
int i, j, k;
static int Used[101], V[101], QIdx;
static int DP[101], tNode;
for(i = 0; i <= N; i++)
Used[i] = 0, V[i] = oo, DP[i] = 0;
Used[st] = 1, V[st] = 0, QIdx = 0, Q[QIdx] = st;
for(i = 0; i <= QIdx; i++) {
tNode = Q[i], Used[tNode] = 0;
for(j = 0, k = NodeL[tNode]; j < NodeT[tNode]; j++, k++) {
if(V[tNode] + Path[k].v < V[Path[k].y]) {
V[Path[k].y] = V[tNode] + Path[k].v;
if(!Used[Path[k].y]) {
Used[Path[k].y] = 1, Q[++QIdx] = Path[k].y;
}
}
}
}
return V[ed];
}
int main() {
int N, M, i;
while(scanf("%d %d", &N, &M) == 2) {
for(i = 0; i <= 100; i++)
NodeL[i] = oo, NodeT[i] = 0;
for(i = 0; i < M; i++) {
scanf("%d %d", &Path[i].x, &Path[i].y);
Path[i].v = 1;
}
qsort(Path, M, sizeof(Pair), cmp);
for(i = 0; i < M; i++) {
NodeL[Path[i].x] = Min(i, NodeL[Path[i].x]);
NodeT[Path[i].x] ++;
}
puts(SPFA(0, N, 100) != oo ? "Ok!" : "Impossib1e!");
}
return 0;
}
上一篇：a279. 分糖果囉
下一篇：a282. 認真念書