Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用SPFA做的代码,不过用了600毫秒,很慢,希望高手指点一下#include <iostream> using namespace std; const int MAXVERTEX = 1000; const int MAXEDGE = 100000; struct Edge{ Edge* next; int vertex; int length; }; class Queue{ public: Queue() :size(MAXVERTEX + 1) {} void init(){ rear = 0; front = 0; } bool enqueue( int v ){ if( (rear + 1)%size != front ){ queue[rear] = v; rear = (rear + 1 )%size; return true; } return false; } bool dequeue( int& v ){ if( rear != front ){ v = queue[front]; front = ( front + 1 )%size; return true; } return false; } private: const int size; int queue[MAXVERTEX+1]; int rear; int front; }; struct Distance{ int length; int count; }; // return true if modified, false if not modified bool relax( const int v, const Edge* e, Distance dist[] ){ if( dist[v].length + e->length < dist[e->vertex].length ){ dist[e->vertex].length = dist[v].length + e->length; return true; } return false; } // return true if has no negative circles // false if has bool spfa( int n, Queue& q, Edge* edge[], Distance dist[], bool isInQueue[] ){ memset( dist, 0, sizeof( Distance ) * (n+1) ); q.init(); for( int k = 1; k <= n; k ++ ){ q.enqueue( k ); isInQueue[k] = true; } int curVertex; n -= 2; while( q.dequeue( curVertex ) ){ isInQueue[curVertex] = false; for( const Edge* temp = edge[curVertex]; temp != NULL; temp = temp->next ){ if( relax( curVertex, temp, dist ) ){ if( !isInQueue[temp->vertex] ){ if( dist[temp->vertex].count > n ) return false; isInQueue[temp->vertex] = true; q.enqueue( temp->vertex ); dist[temp->vertex].count++; } } } } return true; } int main(){ Edge* edgeStore = new Edge[MAXEDGE*2]; Edge** edge = new Edge*[MAXVERTEX+1]; Distance* dist = new Distance[MAXVERTEX+1]; bool isInQueue[MAXVERTEX +1]; Queue q; int n, m; while ( scanf( "%d%d%*c", &n, &m ) != EOF ){ memset( edge, 0, sizeof( Edge* ) * (n +1) ); int top = 0; for( int j = 0; j < m; j ++ ){ char ch; scanf( "%c", &ch ); if( ch == 'P' ){ int a, b, d; scanf( "%d%d%d%*c", &a, &b, &d ); Edge* curPtr = edgeStore + top++; curPtr ->vertex = b; curPtr ->length = -d; curPtr ->next = edge[a]; edge[a] = curPtr; Edge* curPtr2 = edgeStore + top++; curPtr2 ->vertex = a; curPtr2 ->length = d; curPtr2 ->next = edge[b]; edge[b] = curPtr2; } else{ int a, b; scanf( "%d%d%*c", &a, &b ); Edge* curPtr = edgeStore + top++; curPtr ->vertex = b; curPtr ->length = -1; curPtr ->next = edge[a]; edge[a] = curPtr; } } if( spfa( n, q, edge, dist, isInQueue ) ) printf( "Reliable\n" ); else printf( "Unreliable\n" ); } delete[] dist; delete[] edgeStore; delete[] edge; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator