1. 题目

传送门＝￣ω￣＝
题目大意：给你一张有向图，求点 1 到其他点和其他点到点 1 的最短路长度之和。
节点数、边数在 10^6 以内

题解

此题卡常。
用真正链表会超时，因为真链表会动态申请空间。
stl 更不用说。
得用模拟链表。

至于思路，很简单，建立反向图，在原图、反向图上分别跑一下 spfa。
最后求最短路之和。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
static const int maxs=1000000;
template<typename _Tp>inline void in(_Tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct graph
{
    int to[maxs+5],dis[maxs+5],nxt[maxs+5],head[maxs+5],size;
    inline graph(){memset(head,-1,sizeof(head)),size=0;}
    inline void push(int u,int v,int w)
    {
        to[size]=v,dis[size]=w,nxt[size]=head[u],head[u]=size,size++;
    }
}l,ul;
int n,m;
LL dis[maxs+5],ans;
queue<int> que;
bool inque[maxs+5];
void spfa(graph*l)
{
    for(int i=2;i<=n;i++)dis[i]=LLONG_MAX;
    que.push(1),inque[1]=1;
    while(!que.empty())
    {
        int f=que.front();que.pop(),inque[f]=0;
        for(int i=l->head[f];i!=-1;i=l->nxt[i])
            if(dis[l->to[i]]>dis[f]+l->dis[i])
            {
                dis[l->to[i]]=dis[f]+l->dis[i];
                if(!inque[l->to[i]])que.push(l->to[i]),inque[l->to[i]]=1;
            }
    }
    for(int i=2;i<=n;i++)ans+=dis[i];
}
int main()
{
    in(n),in(m);
    for(int i=1,u,v,w;i<=m;i++)in(u),in(v),in(w),l.push(u,v,w),ul.push(v,u,w);
    spfa(&l),spfa(&ul),printf("%lld\n",ans);
    return 0;
}