【u017】请柬

Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。　　这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。　学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

【输入格式】

第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。总部在第1个站点，价钱都是整数，且小于1000000000。

【输出格式】

输出一行，表示最小费用。

【数据规模】

Sample Input1

Sample Output1

【样例说明】

学生各自从总部被派遣到2,3,4站点，然后又回到总部

1-2-4-1:10+5+50=65

1-3-4-1:20+10+50=80

1-2-4-1:10+5+50=65

65+80+65=210

此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数。


【题解】

这题的图算是比较的密集的图。如果用spfa的话。第一个点无法通过。而应该用dijkstra+堆优化来实现。

因为后者更擅长解决密集的图的问题。

做法是这样。

一开始输入图的时候，建一个正图和一个反图。

然后分别在正图和反图上做从起点1到其他点的最短路。

然后获取的dis[0][1..n],dis[1][1..n]分别表示在正图和反图上1到其他点的最短路。

最后答案累加dis[0][i]+dis[i](i∈[2..n])；

难点在dijkstra的堆优化(堆操作)

【代码】
#include <cstdio>

#include <cstring>

struct data

{

	int from;

};

int n, m, first[2][1000001], next[2][1000001] = { 0 }, en[2][1000001], tot[2] = { 0 };

__int64 cost[2][1000001], dis[2][1000001] = { 0 },ans = 0;//0是正图，1是反图 邻接表存储！。

int sizedui,now,nali[1000001],pos;

data dui[1000001];//堆

void up_adjust(int p)//从p开始往上调整堆

{

	__int64 x = dis[now][dui[p].from];//先取得这个堆这个位置上的数据 只要记录下标就好。

	data temp = dui[p]; //作为temp整个记录dui[p] ->其实等价记录下标。

	int i = p, j = p / 2;

	while (j > 0)//如果没有超过堆的范围

	{

		if (x < dis[now][dui[j].from])//如果要调整则调整

		{

			nali[dui[j].from] = i;//要记录这个下标在堆中的位置

			dui[i] = dui[j];//调整

			i = j;

			j = i / 2;

		}

		else

			break;

	}

	dui[i] = temp;//把它赋值到新的位置上。

	nali[temp.from] = i;//更新它在堆中的位置。

}

void down_adjust(int p)//把堆中的数据从p开始往下调整

{

	__int64 x = dis[now][dui[p].from];//同样获取这个数据

	data temp = dui[p];//先用temp存下来。

	int i = p, j = p * 2;

	while (j <= sizedui)//如果没有超过堆的范围。

	{

		if (j < sizedui && dis[now][dui[j + 1].from] < dis[now][dui[j].from])//如果j+1指向数据更小

			j++;//则递增j

		if (x > dis[now][dui[j].from])//如果需要调整

		{

			nali[dui[j].from] = i;//改变j在堆中的位置,在外面要用一个数组记录。

			dui[i] = dui[j];//调整

			i = j;

			j = i * 2;

		}

		else

			break;

	}

	dui[i] = temp;//调整到新的位置(如果要)

	nali[temp.from] = i;//改变它在nali数组中记录的位置。

}

void dijkstra(int fx) //fx == 0 表示正方向 fx==1表示反方向。

{

	memset(nali, 0, sizeof(nali));//nali数组要初始化。

	memset(dis[fx], 255, sizeof(dis[fx]));//fx一开始赋值为-1，表示正无穷

	now = fx; //这是用于向上调整过程和向下调整过程中记录当前图的方向。

	sizedui = 1;//堆的大小。

	dis[fx][1] = 0;//初始化dis[0] == 0;

	dui[sizedui].from = 1;//在堆中的数据

	nali[1] = 1;//一开始在1位置

	bool bo[1000001];//判断某个点是否已经找到最短距离

	memset(bo, false, sizeof(bo));//初始化都没找到最短距离

	for (int i = 1; i <= n; i++)

	{

		if (sizedui == 0) //如果堆中已经不存在数据了。则结束程序、表示都找到了。

			break;

		int k = dui[1].from;//取出堆顶的最小的元素。

		nali[k] = 0;//把k在堆中的位置置为0

		dui[1] = dui[sizedui];//把堆底的元素放到堆顶。

		sizedui--;

		down_adjust(1);//从堆底往下调整。

		bo[k] = true;//表示k已经找到了最短路

		int temp = first[fx][k];//找k元素的出度

		while (temp != 0)

		{

			int y = en[fx][temp];//获取其一个出度

			__int64 w = cost[fx][temp];//获取这条路径的花费。

			if (!bo[y] && (dis[fx][y] == -1 || dis[fx][y] > dis[fx][k] + w))

			{//如果该出度未找到最短路 且其为无穷大或能够更新dis值。

				dis[fx][y] = dis[fx][k] + w;//更新dis值

				if (nali[y] != 0)//如果它已经在堆中了

				{

					up_adjust(nali[y]);//就尝试先往上调整(因为会变大，所以实则只需往下调整);

					down_adjust(nali[y]);//再尝试往下调整

				}

				else

				{

					sizedui++;

					dui[sizedui].from = y;//如果不在堆中。就把它加到堆的堆底。

					nali[y] = sizedui;//更新其在堆中的位置.

					up_adjust(sizedui);//先往上调整。

					down_adjust(nali[y]);//再往下调整。

				}

			}

			temp = next[fx][temp];//找下一个出度

		}

	}

}

int main()

{

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= m; i++)//用邻接表来存正图和反图

	{

		int x, y, z;

		scanf("%d%d%d", &x, &y, &z);

		tot[0]++;//链式存储存正图

		next[0][tot[0]] = first[0][x];

		first[0][x] = tot[0];

		en[0][tot[0]] = y;

		cost[0][tot[0]] = z;

		tot[1]++;//链式存储存反图。

		next[1][tot[1]] = first[1][y];

		first[1][y] = tot[1];

		en[1][tot[1]] = x;

		cost[1][tot[1]] = z;

	}

	dijkstra(0);//在正图和反图上做最短路

	dijkstra(1);

	for (int i = 2; i <= n; i++)//最后输出到达和返回的最短路的和即可。

		ans += (dis[0][i] + dis[1][i]);

	printf("%I64d\n", ans);

	return 0;

}

巴特西