3058473_wa.cc

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

#include <stdio.h>
#include <algorithm>
#define MAX 50001

#define INIT (Node *)malloc(sizeof(Node))

using namespace std;

unsigned __int64 INF = (unsigned __int64)(1)<<63;

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

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

int n, m;
int heap[MAX];
int mark[MAX];
unsigned __int64 num[MAX], dis[MAX];

void read_map()
{
	int i;
	int a, b;
	unsigned __int64 c;

	scanf("%d%d",&n,&m);
	for(i = 0; i < n; i++)
	{
		scanf("%I64u",&num[i]);
		graph[i].head = INIT;
		graph[i].head->next = NULL;
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%I64u",&a,&b,&c);
		if(a==b)
			continue;
		a--,b--;
		Node *p;
		p = INIT;
		p->w = c;p->id = a;
		p->next = graph[b].head->next;
		graph[b].head->next = p;
		p = INIT;
		p->w = c;p->id = b;
		p->next = graph[a].head->next;
		graph[a].head->next = p;
	}
}

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

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

	if(n==0)
	{
		puts("0");
		return ;
	}
	for(i = 0; i < n; i++)
		dis[i] = INF;
	r = 0;
	heap[r] = 0;
	dis[0] = 0;
	r++;
	memset(mark,0,sizeof(mark));
	while(r > 0)
	{
		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;
		}
	}
	unsigned __int64 ans = 0;
	for(i = 1; i < n; i++)
	{
		if(dis[i]==INF)
		{
			puts("No Answer");
			return ;
		}
		ans += num[i]*dis[i];
	}
	printf("%I64u\n",ans);
}


int main()
{
	int cas;

	INF = INF-1+INF;
	scanf("%d",&cas);
	while(cas--)
	{
		read_map();
		dijkstra();
	}
	return 0;
}