| ||||||||||
| 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