2011-10-29 06:59:20Morris
a259. Q10917: A Walk Through the Forest
a259. Q10917: A Walk Through the Forest
作法 : SPFA + DP
搜尋所有點到 2 的距離，接著使用 DP，計算到點 1 的方法數
/**********************************************************************************/
/* Problem: a259 "Q10917: A Walk Through the Forest" from UVa/ACM , Lucky cat 翻譯*/
/* Language: C (1888 Bytes) */
/* Result: AC(440ms, 608KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 14:26:37 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 1000000000
typedef struct {
int x, y, v;
}Pair;
Pair Path[1000000];
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[1001], NodeL[1001], Q[1000001];
int SPFA(int st, int ed, int N) {
int i, j, k;
static int Used[1001], V[1001], QIdx;
static int DP[1001], tNode;
for(i = 1; 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;
}
}
}
}
static Pair Tmp[1001];
for(i = 1; i <= N; i++)
Tmp[i-1].x = V[i], Tmp[i-1].y = i;;
DP[st] = 1;
qsort(Tmp, N, sizeof(Pair), cmp);
for(i = 0; i < N; i++) {
tNode = Tmp[i].y;
for(j = 0, k = NodeL[tNode]; j < NodeT[tNode]; j++, k++) {
if(V[tNode] < V[Path[k].y] && V[Path[k].y] != oo) {
DP[Path[k].y] += DP[tNode];
}
}
if(tNode == ed) break;
}
return DP[ed];
}
int main() {
int N, M, i;
while(scanf("%d", &N) == 1 && N) {
scanf("%d", &M);
for(i = 1; i <= N; i++)
NodeL[i] = oo, NodeT[i] = 0;
for(i = 0; i < M; i++) {
scanf("%d %d %d", &Path[i].x, &Path[i].y, &Path[i].v);
Path[M+i].x = Path[i].y;
Path[M+i].y = Path[i].x;
Path[M+i].v = Path[i].v;
}
qsort(Path, 2*M, sizeof(Pair), cmp);
for(i = 0, M *= 2; i < M; i++) {
NodeL[Path[i].x] = Min(i, NodeL[Path[i].x]);
NodeT[Path[i].x] ++;
}
printf("%d\n", SPFA(2, 1, N));
}
return 0;
}
內容 ：
Jimmy最近覺得工作壓力很大。為了放鬆心情，他喜歡走路回家。 他的辦公室在森林的一邊，而他的家在森林的另一邊。當他在森林中散步時，看看小鳥、松鼠讓他覺得很快樂。
森 林是那麼的美，Jimmy想要每天都走不同的路徑回家。但是他也不想要回家太晚，所以他總是選擇一條可以朝他家「前進」的路徑來走。所謂「前進」指的是他 會選擇從A點走到B點如果B點存在一條到他家的路徑長度比A點到他家任一路徑的長度都來的短的話。請你算出Jimmy共有多少種不同的路徑可以走。
輸入說明
：
輸入包含多組測試資料。
每組測試資料的第1列包含2個整數 N （ 1 < N <= 1000）和 M，N代表共有多少個點（編號從1到 N，請注意：編號 1 的點為 Jimmy 的辦公室，編號 2 的 點為 Jimmy 的家），M代表共有多少個連接2個點的邊。接下來的M列每列有3個整數 a, b, d。a,b為點的編號，d 為連接 a,b 的路徑長（在這裡 a,b 不會相同，1 <= d <= 1000000）。路徑是雙向的，且任2點之間僅有一條路徑連接。
輸入的最後一列僅有一個 0，請參考Sample Input。
輸出說明
：
每組測試資料輸出一列，Jimmy共有多少種不同的路徑可以走。你可以假設這個數字不會超過2147483647。
範例輸入 ：
5 6 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 24 7 8 1 3 1 1 4 1 3 7 1 7 4 1 7 5 1 6 7 1 5 2 1 6 2 1 5 7 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 25 4 5 1000 2 1 1 2 999 0
範例輸出 ：
2 4 3 1
提示
：
2011/10/23 02:00 am 修正測資，感謝 david942j 提出錯誤，已手動全部重測。
各位非常抱歉！！！
出處
：
UVa/ACM , Lucky cat 翻譯
(管理：m80126colin)
作法 : SPFA + DP
搜尋所有點到 2 的距離，接著使用 DP，計算到點 1 的方法數
/**********************************************************************************/
/* Problem: a259 "Q10917: A Walk Through the Forest" from UVa/ACM , Lucky cat 翻譯*/
/* Language: C (1888 Bytes) */
/* Result: AC(440ms, 608KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 14:26:37 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 1000000000
typedef struct {
int x, y, v;
}Pair;
Pair Path[1000000];
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[1001], NodeL[1001], Q[1000001];
int SPFA(int st, int ed, int N) {
int i, j, k;
static int Used[1001], V[1001], QIdx;
static int DP[1001], tNode;
for(i = 1; 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;
}
}
}
}
static Pair Tmp[1001];
for(i = 1; i <= N; i++)
Tmp[i-1].x = V[i], Tmp[i-1].y = i;;
DP[st] = 1;
qsort(Tmp, N, sizeof(Pair), cmp);
for(i = 0; i < N; i++) {
tNode = Tmp[i].y;
for(j = 0, k = NodeL[tNode]; j < NodeT[tNode]; j++, k++) {
if(V[tNode] < V[Path[k].y] && V[Path[k].y] != oo) {
DP[Path[k].y] += DP[tNode];
}
}
if(tNode == ed) break;
}
return DP[ed];
}
int main() {
int N, M, i;
while(scanf("%d", &N) == 1 && N) {
scanf("%d", &M);
for(i = 1; i <= N; i++)
NodeL[i] = oo, NodeT[i] = 0;
for(i = 0; i < M; i++) {
scanf("%d %d %d", &Path[i].x, &Path[i].y, &Path[i].v);
Path[M+i].x = Path[i].y;
Path[M+i].y = Path[i].x;
Path[M+i].v = Path[i].v;
}
qsort(Path, 2*M, sizeof(Pair), cmp);
for(i = 0, M *= 2; i < M; i++) {
NodeL[Path[i].x] = Min(i, NodeL[Path[i].x]);
NodeT[Path[i].x] ++;
}
printf("%d\n", SPFA(2, 1, N));
}
return 0;
}