1511.cpp

pku 1511 北大ACM网站上的算法题

// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
#include <queue>
using namespace std;
#define INF 999999999999
#define MAXP 1000000

struct Edge
{
	int des;
	int price;
	Edge* nex;
};

struct Queue
{
	enum{SIZE=MAXP+1};
	int buffer[SIZE];
	int front,tail;
	void init()
	{ front=tail=0;}
	void push(int i)
	{
		buffer[tail++]=i;
		if(tail==SIZE) tail=0;
	}
	int pop()
	{
		int tmp=buffer[front++];
		if(front==SIZE) front=0;
		return tmp;
	}
	bool empty()
	{ return tail==front;}
};

Edge edges[MAXP*2];
int memi=0;
Edge* go[MAXP+1];//邻接表
Edge* back[MAXP+1];
char bInQ[MAXP+1];

int N,P,Q;
__int64 MinDis[MAXP+1];


//Queue Que;
void Init()
{
	scanf("%d%d",&P,&Q);
	memset(go,0,sizeof(go));
	memset(back,0,sizeof(back));
	memi=0;
	for (int i=0;i<Q;i++)
	{
		int s,d,p;
		scanf("%d%d%d",&s,&d,&p);
		edges[memi].des=d;
		edges[memi].price=p;
		edges[memi].nex=go[s];
		go[s]=&edges[memi++];

		edges[memi].des=s;
		edges[memi].price=p;
		edges[memi].nex=back[d];
		back[d]=&edges[memi++];
	}
}

__int64 spfa(Edge* LinkList[],int start)
{
	int i;
	queue<int> Que;
//	Que.init();
	Que.push(start);
	memset(bInQ,0,sizeof(bInQ));
	for (i=1;i<=P;i++)
		MinDis[i]=(i==start?0:INF);

	while (!Que.empty())
	{
		int id=Que.front();Que.pop();
		Edge* p=LinkList[id];
		while (p)
		{
			if(MinDis[p->des]>MinDis[id]+(p->price))
			{
				MinDis[p->des]=MinDis[id]+(p->price);
				if (!bInQ[p->des])
					Que.push(p->des);
				bInQ[p->des]=1;
			}
			p=p->nex;
		}
	}
	__int64 sum=0;
	for (i=1;i<=P;i++)
		sum+=MinDis[i];
	return sum;
}

int main(int argc, char* argv[])
{
	scanf("%d",&N);
	for (int i=0;i<N;i++)
	{
		Init();
		__int64 sum=0;
		sum+=spfa(go,1);
		sum+=spfa(back,1);
		printf("%I64d\n",sum);
	}
	return 0;
}