LUOGU P1342 请柬(最短路)

传送门

解题思路

又是一道语文题，弄清楚题意之后其实就能想出来了，从1跑一遍最短路，把$dis[n]$加入答案。在建个反图跑一遍最短路，把$dis[n]_$加入最短路就行了。第一遍是去的时候，第二遍是回的时候。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

using namespace std;

const int MAXN = ;

typedef long long LL;

inline int rd(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}

    while(isdigit(ch))  {x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return f?x:-x;

}

int n,m,head[MAXN],cnt;

int to[MAXN],nxt[MAXN],val[MAXN];

int head_[MAXN],cnt_,val_[MAXN],nxt_[MAXN],to_[MAXN];

LL dis[MAXN],ans;

bool vis[MAXN];

struct Node{

    int w,id;

    friend bool operator<(const Node A,const Node B){

        return A.w>B.w;

    }

};

priority_queue<Node> Q;

inline void add(int bg,int ed,int w){

    to[++cnt]=ed,val[cnt]=w,nxt[cnt]=head[bg],head[bg]=cnt;

}

inline void add_(int bg,int ed,int w){

    to_[++cnt_]=ed,val_[cnt_]=w,nxt_[cnt_]=head_[bg],head_[bg]=cnt_;

}

void dijkstra(){

    memset(dis,0x3f,sizeof(dis));

    Node now;now.id=;now.w=;dis[]=;Q.push(now);

    while(!Q.empty()){

        Node zz=Q.top();Q.pop();int x=zz.id;

        if(dis[x]!=zz.w || vis[x]) continue;vis[x]=;

        for(register int i=head[x];i;i=nxt[i]){

            int u=to[i];

            if(dis[u]<=dis[x]+val[i]) continue;

            dis[u]=dis[x]+val[i];

            now.id=u;now.w=dis[u];Q.push(now);

        }

    }

    for(register int i=;i<=n;i++) ans+=dis[i];

}

void dijkstra_(){

    memset(vis,false,sizeof(vis));

    memset(dis,0x3f,sizeof(dis));

    Node now;now.id=;now.w=;dis[]=;Q.push(now);

    while(!Q.empty()){

        Node zz=Q.top();Q.pop();int x=zz.id;

        if(dis[x]!=zz.w || vis[x]) continue;vis[x]=;

        for(register int i=head_[x];i;i=nxt_[i]){

            int u=to_[i];

            if(dis[u]<=dis[x]+val_[i]) continue;

            dis[u]=dis[x]+val_[i];

            now.id=u;now.w=dis[u];Q.push(now);

        }

    }

    for(register int i=;i<=n;i++) ans+=dis[i];

}

int main(){

    n=rd(),m=rd();int x,y,z;

    for(register int i=;i<=m;i++){

        x=rd(),y=rd(),z=rd();

        add(x,y,z),add_(y,x,z);

    }

    dijkstra(),dijkstra_();cout<<ans;

    return ;

}