3058483_wa.cpp

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

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

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

vector<Node> edge[max];
char num[max][50];

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

priority_queue< node ,vector<node> > q;

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

void reverse(char str[])
{
	int i, l;
	char ch;

	l = strlen(str);
	for(i = 0; i < l/2; i++)
	{
		ch = str[i];
		str[i] = str[l-i-1];
		str[l-i-1] = ch;
	}
}

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

void muti(char Tmp[],char t1[])
{
	int tmp, w, p;
	char ans[800], tt;
	int l1, l2, i, j;

	l1 = strlen(Tmp);
	l2 = strlen(t1);
	for(i = 0; i < l2/2; i++)
	{
		tt = t1[i];
		t1[i] = t1[l2-i-1];
		t1[l2-i-1] = tt;
	}
	p = 1;
	for(i = 0; i < 800; i++)
		ans[i] = '0';
	for(i = 0; i < l2; i++)
	{
		w = 0;
		for(j = 0; j < l1; j++)
		{
			tmp = (Tmp[j]-'0')*(t1[i]-'0')+w;
			tmp += ans[j+i]-'0';
			ans[j+i] = tmp%10+'0';
			w = tmp/10;
		}
		if(w)
			ans[j+i] = '0'+w;
	}
	if(w)
		p = 0;
	ans[j+i-p] = '\0';
	strcpy(Tmp,ans);
}

void add(char a[],char b[])
{
	int i, l, w, t;
	int l1, l2;

	l1 = strlen(a);
	l2 = strlen(b);
	l = l1>l2?l1:l2;
	w = 0;
	for(i = 0; i < l; i++)
	{
		if(i>=l1)
			a[i] = '0';
		if(i>=l2)
			b[i] = '0';
		t = a[i]+b[i]-'0'-'0'+w;
		if(t>=10)
			t%=10,w=1;
		else
			w = 0;
		a[i] = t + '0';
	}
	if(w)
		a[i++] = '1';
	a[i] = '\0';
}

void dijk(int start)
{

	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=start;
	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);
			}
		}
	}
	char ans[100], str[100];
	strcpy(ans,"0");
	for(i = 1; i < N; i++)
	{
		if(dis[i]==INF)
		{
			puts("No Answer");
			return ;
		}
		else
		{
			_i64toa(dis[i],str,10);
			muti(num[i],str);
			add(ans,num[i]);
		}
	}
	reverse(ans);
	puts(ans);
}

int main()
{
	int cas;

	scanf("%d",&cas);
	while(cas--)
	{
		init();
		dijk(0);
	}
	return 0;
}