coreBugZJ

此 blog 已棄。

EOJ 1848 你是ACM嗎？

/*
2

EOJ 1848 你是ACM嗎？
3

----問題描述：
6

隨著中國經(jīng)濟的騰飛，中國的物流產(chǎn)業(yè)迎來了發(fā)展的春天。特別是在上海這樣一個擁有廣闊國內(nèi)腹地的國際化大都市，物流業(yè)以空前的速度膨脹。
8

當(dāng)然是大蛋糕就會吸引許多饞嘴貓，饞嘴貓多了就會有殘酷的競爭。當(dāng)大量資金流入物流產(chǎn)業(yè)時，KOP 集團為了穩(wěn)坐在國內(nèi)物流業(yè)的第一把交椅，決定對現(xiàn)行的運輸方案進行改良，以減少自己的成本同時使其它競爭者知難而退。
9

作為世界100強的KOP集團當(dāng)然知道要找到最優(yōu)運輸方案，肯定得靠數(shù)學(xué)和算法很好的軟件工程師，于是他們理所當(dāng)然地找到華東師范大學(xué)軟件學(xué)院。決定通過贊助一場程序比賽來找出最優(yōu)秀的工程師( ACM : Ace Coding Man )。
10

比賽只有一道題目，是運輸線路的簡單抽象，題意如下：
11

SH 市有N個運輸中轉(zhuǎn)點(簡單標示為 1,2,3,

.,N)，中轉(zhuǎn)點之間可能有一條運輸線路，這條線路有一個特殊的地方就是從A 到B點需要耗費 c1 個單位的查克拉(SH市的貨幣單位)，但從B到A可能需要 c2 個查克拉。當(dāng)然c1不一定等于c2，也能從A到B之后就不能從B返回A了。你可以理解為這些線路是“單向”的。線路總共有 M 條。每天有N-1輛車從KOP集團總部(這里假設(shè)就是標號為1的中轉(zhuǎn)點)，出發(fā)，分別發(fā)往N-1個剩下的中轉(zhuǎn)點，然后當(dāng)天再從所到達的中轉(zhuǎn)點返回。你的任務(wù)就是要求出一天的最小耗費。
12

----輸入：
15

第一行為 C ，表示有C個測試用列。接下來分別為C個測試用列。
17

每個測試用例的格式如下：
18

第一行為兩個整數(shù)，N，M ,分別表示有N個中轉(zhuǎn)點和M條道路。( 1=< N, M <=1000000 .);
19

緊接著的M 行每行有三個值 A B c；分別表示從中轉(zhuǎn)點A到中轉(zhuǎn)點B需要耗費 c 個單位的查克拉。 ( 0<= c <= 1000000000 ).
20

----輸出：
23

你的輸出應(yīng)該包括C行，每行輸出一個值，對應(yīng)于相應(yīng)的用列的最少耗費。
25

----樣例輸入：
28

2
30

2 2
31

1 2 13
32

2 1 33
33

4 6
34

1 2 10
35

2 1 60
36

1 3 20
37

3 4 10
38

2 4 5
39

4 1 50
40

----樣例輸出：
43

46
45

210
46

----分析：
49

*/
51

#include <stdio.h>
54

#include <string.h>
55

#define N 1000009
57

#define M 2000009
58

typedef __int64 Tint;
60

typedef struct __EDGE
62

{
63

int v, w;
64

struct __EDGE *next;
65

} EDGE;
66

EDGE MemEdgeSpace[ M ];
68

int MemEdgeTop;
69

#define MemEdgeInit() MemEdgeTop = 0
70

#define MemEdgeNew() ( MemEdgeSpace + MemEdgeTop++ )
71

typedef struct
73

{
74

EDGE *edgeHead, *edgeTail;
75

} NODE;
76

NODE v1[ N ], v2[ N ];
78

Tint Spfa( NODE * v, int n ){
80

#define OO ( 2123456789i64 * 2123456789i64 )
81

static int q[ N ], qh, qt, inq[ N ], s, i, j;
82

static Tint dist[ N ], tot;
83

static EDGE *p;
84

qh = 0;
85

qt = 1;
86

q[ 0 ] = 1;
87

memset( inq + 1, 0, sizeof(inq[0]) * n );
88

inq[ 1 ] = 1;
89

for( i = n; i > 0; --i ){
90

dist[ i ] = OO;
91

}
92

dist[ 1 ] = 0;
93

while( qh != qt ){
94

s = q[ qh ];
95

inq[ s ] = 0;
96

qh = ( qh + 1 ) % N;
97

for( p = v[ s ].edgeHead; p; p = p->next ){
98

if( dist[ s ] + p->w < dist[ j = p->v ] ){
99

dist[ j ] = dist[ s ] + p->w;
100

if( ! inq[ j ] ){
101

q[ qt ] = j;
102

inq[ j ] = 1;
103

qt = ( qt + 1 ) % N;
104

}
105

}
106

}
107

}
108

109

tot = dist[ 1 ];
110

for( i = n; i > 1; --i ){
111

tot += dist[ i ];
112

}
113

return tot;
114

#undef OO
115

}
116

117

int main(){
118

int i, j, k, n, m, td;
119

EDGE *p;
120

scanf( "%d", &td );
121

while( td-- ){
122

scanf( "%d%d", &n, &m );
123

memset( v1 + 1, 0, sizeof(v1[0]) * n );
124

memset( v2 + 1, 0, sizeof(v2[0]) * n );
125

MemEdgeInit();
126

while( m-- ){
127

scanf( "%d%d%d", &i, &j, &k );
128

#define ADD_EDGE(va,i,j,k) \
129

p = MemEdgeNew();
130

p->v = j;
131

p->w = k;
132

p->next = 0;
133

if( va[ i ].edgeHead ){
134

va[ i ].edgeTail->next = p;
135

va[ i ].edgeTail = p;
136

}
137

else{
138

va[ i ].edgeHead = va[ i ].edgeTail = p;
139

}
140

ADD_EDGE( v1, i, j, k );
141

ADD_EDGE( v2, j, i, k );
142

#undef ADD_EDGE
143

}
144

printf( "%I64d\n", Spfa( v1, n ) + Spfa( v2, n ) );
145

}
146

return 0;
147

}
148

posted on 2012-05-14 16:12 coreBugZJ 閱讀(709) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè)

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: 微軟2014實習(xí)生及秋令營技術(shù)類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1848 你是ACM嗎？