最短路
题意: 强调是有向图 ， n个点（1到n标号）m条边，求出点1到所有点的最短路之和 + 所有点到点1的最短路之和
什么？求一次最短路，然后 x 2 就是答案？ 这样是错的，如果是无向图的话可以这样，因为可以逆回去走。但是有向图显然不是，点1到点a的最短路，和点a到点1的最短路是完全不同的，值不同走过的路径也不同.要求点1到所有点的最短路，直接运行一次最短路即可。但是要求所有点到点1的最短路，难道要对所有点运行一次最短路吗？一看点数就可以否定这个想法。可以这样想，如果点a到点1存在最短路，那么把这条路径的边全部取反，就是点1到点a的最短路了。所有在求了第1次最短路后，将 整个图的边取反，再求一次点1到所有点的最短路就行了，可以知道边都取反后，第一次走过的路径都不会再走到（都取反了），而从点a可能到点1的可能的边都成了点1到点a的可能的边
代码用了spfa算法，用queue和stack来辅助对时间的影响不大，但是stack稍快一点（只从上次后我发现其实stack都比queue快，一般情况下，更不用题特殊情况了）
另外用dij+heap也行，朴素的dij应该是超时的，虽然没写
#include#include #include #include using namespace std;#define N 1000010#define INF 0x3f3f3f3ftypedef long long ll;ll d[N];int n,tot;int head[N];bool ins[N];struct edge{ int u,v,w,next;}e[N],tt[N];void add(int u ,int v ,int w , int k){ e[k].u = u; e[k].v = v; e[k].w = w; e[k].next = head[u]; head[u] = k;}ll spfa_stack(){ stack sta; memset(d,0x3f,sizeof(d)); memset(ins,false,sizeof(ins)); while(!sta.empty()) sta.pop(); d[1] = 0; ins[1] = true; sta.push(1); while(!sta.empty()) { int u = sta.top(); sta.pop(); ins[u] = false; for(int k=head[u]; k!=-1; k=e[k].next) { int v =e[k].v; int w = e[k].w; if( d[u] + w < d[v] ) { d[v] = d[u] + w; if(!ins[v]) { ins[v] = true; sta.push(v); } } } } ll res = 0; for(int i=1; i<=n ; i++) res += d[i]; return res;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&tot); memset(head,-1,sizeof(head)); for(int i=0; i