| 2767343 | 2008-03-02 15:15:48 | Accepted | 2546 | C++ | 00:00.45 | 4364K | C.D.=.= |
写了个最简单的单源路径算法。完全是O(V^2)。比起2281的最小堆+链表差了不止一个档次……
后续还有一个记忆化搜索的处理，当value[u]>value[v]的时候可以把u的路径可能数加到v上。Waterloo的那一次LC还比较简单，加上网站提供标程与数据，已经轻松Clear。
1
#include <cstdio>
2#include <string>
3
4#define MAXN 200000000
5
6int N, M, value[1001], visited[1001], a[1001][1001], num[1001];
7
8int init ();
9void dijk ();
10void dp ();
11int func ( int );
12
13int main ()
14
{
15
//freopen ( "in.txt", "r", stdin );
16 while ( init () )
17
{
18 dijk ();
19 dp ();
20 //print ();
21
}
22 return 0;
23
}
24
25int init ()
26{
27 memset ( a, 0, sizeof ( a ) );
28 scanf ( "%d", &N );
29 if ( !N )
30 return 0;
31 scanf ( "%d", &M );
32 int i, j, tx, ty, tw;
33 for ( i = 0, j = 0; i < M; i ++ )
34 {
35 scanf ( "%d %d %d", &tx, &ty, &tw );
36 a[tx][ty] = tw, a[ty][tx] = tw;
37 }
38 return 1;
39}
40
41void dijk ()
42{
43 int i, j, u;
44 for ( i = 1; i <= N; i ++ )
45 value[i] = MAXN;
46 memset ( visited, 0, sizeof ( visited ) );
47 u = 2, value[u] = 0;
48 for ( i = 1; i < N; i ++ )
49 {
50 visited[u] = 1;
51 // update each point
52 for ( j = 1; j <= N; j ++ )
53 {
54 if ( !visited[j] && a[u][j] && a[u][j] + value[u] < value[j] )
55 value[j] = a[u][j] + value[u];
56 }
57 // find the min
58 int mn = MAXN;
59 for ( j = 1; j <= N; j ++ )
60 {
61 if ( !visited[j] && value[j] < mn )
62 mn = value[j], u = j;
63 }
64 if ( mn == MAXN )
65 break;
66 }
67}
68
69void dp ()
70{
71 if ( value[1] == MAXN )
72 {
73 printf ( "0\n" );
74 return;
75 }
76 memset ( num, 0xff, sizeof ( num ) );
77 num[1] = 1;
78 printf ( "%d\n", func ( 2 ) );
79}
80
81int func ( int v )
82{
83 if ( num[v] != -1 )
84 return num[v];
85 int u, sum = 0;
86 for ( u = 1; u <= N; u ++ )
87 {
88 if ( a[u][v] && value[u] > value[v] )
89 sum += func ( u );
90 }
91 return num[v] = sum;
92}
93
#include <cstdio>2
#include <string>3
4
#define MAXN 2000000005
6
int N, M, value[1001], visited[1001], a[1001][1001], num[1001];7
8
int init ();9
void dijk ();10
void dp ();11
int func ( int );12
13
int main ()14
{15
//freopen ( "in.txt", "r", stdin );16
while ( init () )17
{18
dijk ();19
dp ();20
//print ();21
}22
return 0;23
}24
25
int init ()26
{27
memset ( a, 0, sizeof ( a ) );28
scanf ( "%d", &N );29
if ( !N )30
return 0;31
scanf ( "%d", &M );32
int i, j, tx, ty, tw;33
for ( i = 0, j = 0; i < M; i ++ )34
{35
scanf ( "%d %d %d", &tx, &ty, &tw );36
a[tx][ty] = tw, a[ty][tx] = tw;37
}38
return 1;39
}40
41
void dijk ()42
{43
int i, j, u;44
for ( i = 1; i <= N; i ++ )45
value[i] = MAXN;46
memset ( visited, 0, sizeof ( visited ) );47
u = 2, value[u] = 0;48
for ( i = 1; i < N; i ++ )49
{50
visited[u] = 1;51
// update each point52
for ( j = 1; j <= N; j ++ )53
{54
if ( !visited[j] && a[u][j] && a[u][j] + value[u] < value[j] )55
value[j] = a[u][j] + value[u];56
}57
// find the min58
int mn = MAXN;59
for ( j = 1; j <= N; j ++ )60
{61
if ( !visited[j] && value[j] < mn )62
mn = value[j], u = j;63
}64
if ( mn == MAXN )65
break;66
}67
}68
69
void dp ()70
{71
if ( value[1] == MAXN )72
{73
printf ( "0\n" );74
return;75
}76
memset ( num, 0xff, sizeof ( num ) );77
num[1] = 1;78
printf ( "%d\n", func ( 2 ) );79
}80
81
int func ( int v )82
{83
if ( num[v] != -1 )84
return num[v];85
int u, sum = 0;86
for ( u = 1; u <= N; u ++ )87
{88
if ( a[u][v] && value[u] > value[v] )89
sum += func ( u );90
}91
return num[v] = sum;92
}93
评论