题解 P1342 【请柬】

XZYQvQ · 2017-05-07 10:56:40 · 题解

这题卡常啊。

邻接表不能用手写的真链表，会超时。。。

用stl的链表就更不用说了。

只能手动模拟链表。

因为真链表会动态申请内存，比较慢。。。

至于思路，楼下的已经讲的很清晰了。

建立反向图，以1节点为源点在正反图上分别跑一遍spfa。

答案就是所有点到1节点的最短路长度之和。

代码：

#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++;
    }
};
int n,m;
LL dis[maxs+5],ans;
graph l,ul;
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;
}