解题思路
又是一道语文题，弄清楚题意之后其实就能想出来了，从1跑一遍最短路，把$dis[n]$加入答案。在建个反图跑一遍最短路，把$dis[n]_$加入最短路就行了。第一遍是去的时候，第二遍是回的时候。
#include#include #include #include #include using namespace std;const int MAXN = 1000005;typedef long long LL;inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';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 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=1;now.w=0;dis[1]=0;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]=1; 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=2;i<=n;i++) ans+=dis[i];}void dijkstra_(){ memset(vis,false,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); Node now;now.id=1;now.w=0;dis[1]=0;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]=1; 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=2;i<=n;i++) ans+=dis[i];}int main(){ n=rd(),m=rd();int x,y,z; for(register int i=1;i<=m;i++){ x=rd(),y=rd(),z=rd(); add(x,y,z),add_(y,x,z); } dijkstra(),dijkstra_();cout<