Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。 这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。 学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。【输入格式】
第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。 然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。 总部在第1个站点，价钱都是整数，且小于1000000000。
【输出格式】
输出一行，表示最小费用。
【数据规模】
Sample Input1
4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50
Sample Output1
210
【样例说明】
学生各自从总部被派遣到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 ", ans); return 0; }