例题:
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]+disi；
难点在dijkstra的堆优化(堆操作)
->这里用multiset+它的upper_bound函数来实现堆优化;
注意重载判断的时候要把第二个关键字也照顾到，不然upper_bound会失效
获取multiset的头结点的地址
设h为一个结构体multiset
用
__typeof(h.begin()) c=begin();
c就是头结点的地址;
然后x=(*c)就是头元素;
则可以直接访问结构体里的元素了
x.name
x.point
什么的.
upper_bound出来的类型也一样;
也是__typeof(h.begin())
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;
typedef pair<LL,LL> pll;const int MAXN = 1e6+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);vector <LL> w[2][MAXN];
vector <int> g[2][MAXN];
__int64 dis[2][1000001] = { 0 },ans = 0;//0是正图，1是反图
int n,m;struct rec{
LL dis,x;
friend bool operator < (rec a,rec b)
{
return a.dis < b.dis || (a.dis==b.dis && a.x < b.x);
}
};
multiset<rec>h;void dijkstra(int fx) //fx == 0 表示正方向 fx==1表示反方向。
{
memset(dis[fx],255,sizeof dis[fx]);
dis[fx][1] = 0;//初始化dis[0] == 0;
h.clear();
h.insert({0,1});
while (!h.empty())
{
__typeof(h.begin()) c=h.begin();
rec tou = (*c);
h.erase(c);
int x = tou.x;
int len = g[fx][x].size();
rep1(i,0,len-1)
{
int y = g[fx][x][i];
LL co = w[fx][x][i];
if (dis[fx][y] == -1)
{
dis[fx][y] = dis[fx][x] + co;
h.insert({dis[fx][y],y});
}
else
if (dis[fx][y] > dis[fx][x] + co)
{
c = h.upper_bound({dis[fx][y],y});c--;h.erase(c);
dis[fx][y] = dis[fx][x]+co;
h.insert({dis[fx][y],y});
}
}
}
}int main()
{
//freopen("F:\\rush.txt","r",stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)//用邻接表来存正图和反图
{
int x, y;LL z;
rei(x);rei(y);rel(z);
g[0][x].pb(y);
w[0][x].pb(z);
g[1][y].pb(x);
w[1][y].pb(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;
}
