#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

struct Node
{
	Node(int i, int value, Node *next = NULL)
	{
		this->i = i;
		this->value = value;
		this->next = next;
	}
	int i;
	int value;
	Node *next;
};

int n, m;
const int N = 30010;
const int Inf = 0x7fffffff;
Node *G[N];
int d[N];
bool visit[N];

int queue[N*100];
int cur;

void destroy(Node **G, int size)
{
	for(int i = 0; i < size; i++)
	{
		Node *p = G[i];
		while(p)
		{
			G[i] = p->next;
			delete p;
			p = G[i];
		}
	}
}

void printQueue()
{
	printf("\nstack: ");
	for(int i = 0; i < cur; i++)
		printf("%d ", queue[i]);
	printf("\n\n");
}

int Priority(const int id)
{
	return d[queue[id]];
}

void FixUp(const int id)
{
	int i = id, j = (i-1)>>1;
	int pri = Priority(id);
	int item = queue[id];
	
	while( i > 0 && pri < Priority(j) )
	{
		queue[i] = queue[j];
		i = j;
		j = (i-1)>>1;
	}
	queue[i] = item;
}

void FixDown(const int id)
{
	int	i = id, j = i+i+1;
	int pri = Priority(id);
	int item = queue[id];
	
	while(j < cur)
	{
		if( j+1 < cur && Priority(j+1) < Priority(j) )		//取小
			j++;
		if( Priority(j) >= pri )
			break;
		queue[i] = queue[j];
		i = j;
		j = i+i+1;
	}
	
	queue[i] = item;
}

void Push(const int item)
{
	queue[cur] = item;
	FixUp(cur);
	cur++;
	
//	printQueue();
}

int Pop()		//最前最小
{
	if(cur == 0)
		return queue[0];
	int item = queue[0];
	queue[0] = queue[--cur];
	FixDown(0);
//	printQueue();
	
	return item;
}

bool Empty()
{
	return (cur == 0);
}

void Reset()
{
	cur = 0;
}

int weight(int u, int v)
{
	Node *p = G[u];
	while(p)
	{
		if(p->i == v)
			break;
		p = p->next;
	}
	if(p)
		return p->value;
	return Inf;
}

void init(int src)
{
	for(int i = 1; i <= n; i++)
		d[i] = Inf;
	d[src] = 0;
	Reset();
	Push(src);
}

void relax(int u, int v)
{
	if(d[u] == Inf)
		return;
	int w = weight(u, v);
	if(w == Inf)
		return;

	if(d[v] > d[u]+w)
	{
		d[v] = d[u]+w;
		Push(v);
	}
}

void print()
{
	printf("\nd: ");
	for(int i = 1; i <= n; i++)
		printf("%d ", d[i]);
	printf("\n\n");
}

void Dijkstra()
{
	while( !Empty() )
	{
		int u = Pop();
		while(visit[u])
		{
			if( Empty() )
				return;
			u = Pop();
		}
		
		visit[u] = true;
		for(Node *p = G[u]; p; p = p->next)
		{
			if(visit[p->i])
				continue;
			relax(u, p->i);
		}

//		print();
	}
}


int main()
{
	while(scanf("%d%d", &n, &m) != EOF)
	{
		for(int i = 0; i < m; i++)
		{
			int begin, end, value;
			scanf("%d%d%d", &begin, &end, &value);
			G[begin] = new Node(end, value, G[begin]);
		}

		int src = 1;
		int dst = n;

		init(src);
//		print();
		Dijkstra();
//		print();
		printf("%d\n", d[dst]);

		destroy(G, N);
		memset(visit, 0x00, sizeof(visit));
	}
}

• Re:为什么老是wa，罪过啊。附上代码请强人帮忙看看，谢谢！ (1750) richardxx 2007-01-20 17:56:45
  • Re:为什么老是wa，罪过啊。附上代码请强人帮忙看看，谢谢！ (2084) badboy 2007-01-20 23:12:32
    • 正确答案是4,我的代码发给你了 (0) TopBoy 2007-01-21 10:17:20