2840251_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MAX 2000010
#define INIT (Node *)malloc(sizeof(Node))
#define INF 21000000000000
using namespace std;

int n;

typedef struct node
{
	int id;
	__int64 w;
	struct node *next;
}Node;

struct NODE
{
	Node *head;
}graph[MAX];

int heap[MAX], mark[MAX];;
__int64 dis[MAX];

bool cmp(int a,int b)
{
	return dis[a]>dis[b];
}

void dijkstra(int s,int t)
{
	int i, u, r;

	for(i = 0; i <= 2*n+1; i++)
		dis[i] = INF;
	r = 0;
	heap[r] = s;
	dis[s] = 0;
	r++;
	memset(mark,0,sizeof(mark));
	while(!mark[t])
	{
		u = heap[0];
		pop_heap(heap,heap+r,cmp);
		r--;
		if(mark[u])
			continue;
		mark[u] = 1;
		Node *p;
		p = graph[u].head;
		while (p->next)
		{
			if(!mark[p->next->id]&&dis[u]+p->next->w<dis[p->next->id])
			{
				dis[p->next->id] = dis[u] + p->next->w;
				heap[r] = p->next->id;
				r++;
				push_heap(heap,heap+r,cmp);
			}
			p = p->next;
		}
	}
	printf("%I64d\n",dis[t]);
}

void init()
{
	int i;
	__int64 w;
	Node *p;
	int st, ed, a, b;

	for(i = 0; i <= 2*n+1; i++)
	{
		graph[i].head = INIT;
		graph[i].head->next = NULL;
	}
	scanf("%d%d%d%d",&a,&st,&b,&ed);
	if(a)
		st += n+1;
	if(b)
		ed += n+1;
	for(i = 0; i < n; i++)
	{
		scanf("%I64d",&w);
		p = INIT;
		p->w = w;p->id = i+1;
		p->next = graph[i].head->next;
		graph[i].head->next = p;
		p = INIT;
		p->w = w;p->id = i;
		p->next = graph[i+1].head->next;
		graph[i+1].head->next = p;
	}
	for(i = 0; i <= n; i++)
	{
		scanf("%I64d",&w);
		p = INIT;
		p->w = w;p->id = i+n+1;
		p->next = graph[i].head->next;
		graph[i].head->next = p;
		p = INIT;
		p->w = w;p->id = i;
		p->next = graph[i+n+1].head->next;
		graph[i+n+1].head->next = p;
	}
	for(i = n+1; i <= 2*n; i++)
	{
		scanf("%I64d",&w);
		p = INIT;
		p->w = w;p->id = i+1;
		p->next = graph[i].head->next;
		graph[i].head->next = p;
		p = INIT;
		p->w = w;p->id = i;
		p->next = graph[i+1].head->next;
		graph[i+1].head->next = p;
	}
	dijkstra(st,ed);
}

int main()
{
	while(scanf("%d",&n)==1,n)
	{
		init();
	}
	return 0;
}