霉利的题解（2）

· · 题解

这道题我们可以发现可以分为两个部分。

  1. 第一是学生去车站的部分。（一点到多点，dij或spfa）
  2. 第二是学生从车站回来。（多点到一点）

我们如果可以将图反着存，那么就可以将多点到一点变成一点到多点。

代码如下

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,m,x,y,l,dis[N],dis1[N],f[N],f1[N],pre[N],pre1[N],cnt,cnt1,q[5*N],q1[5*N],sum=0;//因为要有正反两图，所以我们要定义双份；
struct edge{
    ll f,t,l,n;
}a[5*N],b[5*N];
void add(ll x,ll y,ll l){
    a[++cnt].f=x;
    a[cnt].t=y;
    a[cnt].l=l;
    a[cnt].n=pre[x];
    pre[x]=cnt;
}//链式前向星(正图)
void add1(ll y,ll x,ll l){
    b[++cnt1].f=y;
    b[cnt1].t=x;
    b[cnt1].l=l;
    b[cnt1].n=pre1[y];
    pre1[y]=cnt1;
}//链式前向星（反图）
//正图spfa模版
void spfa(){
    ll head=1,tail=1;
    q[1]=1;
    f[1]=1;
    dis[1]=0;
    while(head<=tail){
        ll from=q[head];
        for(int i=pre[from];i;i=a[i].n){
            ll to=a[i].t;
            ll len=a[i].l;
            if(dis[from]+len<dis[to]){
                dis[to]=dis[from]+len;
                if(f[to]==0){
                    f[to]=1;
                    q[++tail]=to;
                }
            }
        }
        f[from]=0;
        head++;
    }
}
//反图spfa
void spfa1(){
    ll head=1,tail=1;
    q1[1]=1;
    f1[1]=1;
    dis1[1]=0;
    while(head<=tail){
        ll from=q1[head];
        for(int i=pre1[from];i;i=b[i].n){
            ll to=b[i].t;
            ll len=b[i].l;
            if(dis1[from]+len<dis1[to]){
                dis1[to]=dis1[from]+len;
                if(f1[to]==0){
                    f1[to]=1;
                    q1[++tail]=to;
                }
            }
        }
        f1[from]=0;
        head++;
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&x,&y,&l);
        add(x,y,l);//正着存入
        add1(y,x,l);//反着存入
    }
    for(int i=1;i<=n;i++){
        dis[i]=2e9+10;
        dis1[i]=2e9+10;
    }//初始化
    spfa();
    spfa1();
    for(int i=2;i<=n;i++){
        sum+=dis[i]+dis1[i];//将所有的点费用加起来
    }
    printf("%lld",sum);
}

注意要用快读或者c的输入输出，不然只有小概率得满分（为了保险起见最好加上） 作者亲自实践:(