AcWing 4246. 最短路径和（反向建图+链式前向星+堆优化）

题目连接

https://www.acwing.com/problem/content/description/4249/

http://poj.org/problem?id=1511

思路

其实这道题和农场派对这题是一样的，我们反向建边就能求出所有其他点到1这个点的距离，然后直接加上去就好了，但是不同的是这题的数据非常大，所以如果你是使用vector或者其他容器存储的话是会MLE的，所以我们这里手写链式前向星然后每次跑DJ的时候注意初始化就好了，下面放出两种写法的代码（第二种是MLE的）

代码 链式前向星+堆优化Djakarta

#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
const int N=2e6+5;//数据范围
struct edge{//存储边
	int u,v,w,next;//u为起点，v为终点，w为权值，next为前继
};
edge e[N];
int head[N],dis[N],n,m,s,cnt;//head为链中最上面的，dis表示当前答案，n为点数，m为边数，s为起点，cnt记录当前边的数量
bool vis[N];//vis表示这个点有没有走过
struct node{
	int w,to;//w表示累加的权值，to表示到的地方
	bool operator dis[u]+e[i].w){//若中转后更优，就转
				dis[v]=dis[u]+e[i].w;//更新
				q.push(node{dis[v],v});//压入队列
			}
		}
	}
}
int U[N],V[N],W[N];

void init(){
	int l = max(n,m);
	for(int i = 1;i U[i]>>V[i]>>W[i];
			E[U[i]].push_back({V[i],W[i]});//正向建图
			E[v].push_back({u,w});//反向建图
		}
		long long ans = 0;
		DJ(1);
		for(int i = 1;i