Perhaps the reason for getting TLE is because I have used some code from STL in my code. However, I dont think that is gonna make my program TLE. Any suggestions? Guys?

#include <iostream>
#include <vector>
using namespace std;

const int SIZE = 30001;
const int INFINITE = 0x7f7f7f7f;

class Edge
{
public:
	int w, node;
public:
	Edge ()
	{
		Edge ( 0, 0 );
	}
	Edge ( int a, int b )
	{
		w = a;
		node = b;
	}
	bool operator < ( const Edge b )
	{
		return this->w < b.w;
	}
};

class Minheap
{
private:
	Edge nodes[SIZE];
public:
	int size;
	Minheap ()
	{
		size = 0;
	}
private:
	void swap ( Edge& a, Edge& b )
	{
		Edge t = a;
		a = b;
		b = t;
	}

	void heapfy ( int );
public:
	void push ( Edge );
	void pop ();
	Edge front ()
	{
		return nodes[1];
	}
};

void Minheap::push( Edge edge )
{
	size++;
	nodes[size] = edge;

	int i = size;
	while ( i > 1 && ( nodes[i] < nodes[i / 2] ) )
	{
		swap ( nodes[i / 2], nodes[i] );
		i = i / 2;
	}
}

void Minheap::pop()
{
	if ( size < 1 )
		return;

	nodes[1] = nodes[size];
	size--;
	heapfy ( 1 );
}

void Minheap::heapfy( int index )
{
	int l = index * 2, r = l + 1, smaller = index;

	if ( l <= size && nodes[l] < nodes[index] )
		smaller = l;
	if ( r <= size && nodes[r] < nodes[smaller] )
		smaller = r;

	if ( smaller != index )
	{
		swap ( nodes[smaller], nodes[index] );
		heapfy ( smaller );
	}
}

int dist[SIZE], n, m;
bool used[SIZE];

class Graph
{
public:
	vector <Edge> adj[SIZE];
public:
	void addnode ( int, int, int );
};

void Graph::addnode ( int s, int t, int w )
{
	Edge edge ( w, t );
	adj[s].push_back( edge );
}

Graph graph;
Minheap heap;

void read()
{
//	freopen ( "3159.txt", "r", stdin );
	scanf ( "%d%d", &n, &m );
	int s, t, w;

	for ( int i = 0; i < m; i++ )
	{
		scanf ( "%d%d%d", &s, &t, &w );
		graph.addnode( s, t, w );
	}
}

void dijtra ()
{
	memset ( dist, 0x7f, sizeof ( dist ) );
	memset ( used, false, sizeof ( used ) );

	Edge first ( 0, 1 );
	heap.push ( first );
	dist[first.node] = 0;

	while ( heap.size >= 1 )
	{
		Edge e = heap.front();
		heap.pop();

		if ( used[e.node] )
			continue;
		if ( e.node == n )
			break;

		used[e.node] = true;
		for ( int i = 0; i < graph.adj[e.node].size(); i++ )
		{
			Edge t = graph.adj[e.node].at( i );

			if ( !used[t.node] )
			{
				if ( dist[e.node] + t.w < dist[t.node] )
					dist[t.node] = dist[e.node] + t.w;

                t.w = dist[t.node];
				heap.push( t );
			}
		}
	}

	printf ( "%d\n", dist[n] );
}

int main()
{
	read ();
	dijtra ();
	return 0;
}

• 用getchar 200ms scanf900ms (0) angelk700 2008-10-29 20:14:56