3058488_ac_640ms_6080k.cpp

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

#include <stdio.h>
#include <vector>
#include <queue>
#define max 50001
using namespace std;
 
unsigned __int64 INF = (unsigned __int64)(1)<<63;

int N, M;
struct Node
{
	int tar;
	unsigned __int64 value;
};

unsigned __int64 sum, num[max];
vector<Node> edge[max];

struct node
{
	unsigned __int64 value;
	int tar;
 
	bool operator < (const node & x) const
	{
		if (value>x.value) return true;
		return false;
	}
};

priority_queue< node ,vector<node> > q;

unsigned __int64 dis[max];
bool used[max];


void init()
{
	int i, j, k;
	unsigned __int64 w;
 
	scanf("%d%d",&N,&M);
	sum = 0;
	for(i = 0; i < N; i++)
	{
		scanf("%I64u",&num[i]);
		edge[i].clear();
	}
	for (i = 0; i < M; i++)
	{
		scanf("%d%d%I64u",&j,&k,&w);
		if(j==k)
		{
			continue;
		}
		Node t;
		j--;k--;
		t.tar = k;t.value = w;
		edge[j].push_back(t);
		t.tar = j;
		edge[k].push_back(t);
	}
}


void dijk()
{

	int i, j, k;
	
	while (!q.empty()) 
	{
		q.pop();
	}
 
	for (i = 0; i < N; ++i) 
	{
		dis[i]=INF;
	}
	memset(used,false,sizeof(used));
	node temp, temp2;
	temp.value = 0;
	temp.tar = 0;
	q.push(temp);
 
	while (!q.empty())
	{
		while (!q.empty() && used[q.top().tar]) q.pop();
		if (q.empty()) break;
		temp = q.top();
		q.pop();

		used[temp.tar] = true;
		dis[temp.tar] = temp.value;

		for (k = 0; k < edge[temp.tar].size(); k++) 
		{
			j = edge[temp.tar][k].tar;
			if (dis[temp.tar]+edge[temp.tar][k].value< dis[j] && !used[j])
			{
				dis[j] = dis[temp.tar]+edge[temp.tar][k].value;
				temp2.tar = j;
				temp2.value = dis[j];
				q.push(temp2);
			}
		}
	}
	for(i = 1; i < N; i++)
	{
		if(dis[i]==INF)
		{
			puts("No Answer");
			return ;
		}
		sum += num[i]*dis[i];
	}
	printf("%I64u\n",sum);
}

int main()
{
	int cas;

	INF = INF-1+INF;
	//printf("%I64u\n",INF); INF = 18446744073709551615
	scanf("%d",&cas);
	while(cas--)
	{
		init();
		dijk();
	}
	return 0;
}