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 );1213int main ()14{15 //freopen ( "in.txt", "r", stdin );16 while ( init () )17 {18 dijk ();19 dp ();20 //print ();21 }22 return 0;23}2425int 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}4041void 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}6869void 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}8081int 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
评论