做了这个题我突然发现理解算法是思想，不是模板，这个题因为怕超时，朋友都是用spfa做的，我用了dijk 不过不是模板，有点不一样，不过思想一样 题意：就是给你一个N个点的图，求1点到其他每个点最短路权值之和，然后再求反向最短路（其他所有点到1点最短距离）之和，输出两者之和。 代码：
#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; #define N 1000100 #define INF 0x3fffffff struct node { int u,v,next; long long w; bool operator<(const node t)const { return t.w<w; } } e[N],e1[N]; long long dis[N],vis[N],dis1[N]; int first[N],first1[N]; int cnt,cnt1; int n,m; void init() { memset(first,-1,sizeof(first)); memset(first1,-1,sizeof(first1)); memset(dis,0,sizeof(dis)); memset(dis1,0,sizeof(dis1)); cnt=0; cnt1=0; } void add(int u,int v,int w)//把一号点到其他店的路都存起来 { e[cnt].u=u; e[cnt].v=v; e[cnt].next=first[u]; e[cnt].w=w; first[u]=cnt++; } void add1(int u,int v,int w)//把其他点到一号点的路存起来 { e1[cnt1].u=u; e1[cnt1].v=v; e1[cnt1].next=first1[v]; e1[cnt1].w=w; first1[v]=cnt1++; } priority_queue<node> que; int main() { node cur,nwnode; int t,v,u; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); for(int i=0; i<m; i++) { int x,y,key; scanf("%d%d%d",&x,&y,&key); add(x,y,key); add1(x,y,key); } memset(vis,0,sizeof(vis)); while(!que.empty()) que.pop(); for(int i=first[1]; i!=-1; i=e[i].next) { que.push(e[i]); } vis[1]=1; while(!que.empty())//一号点到其他点的最短路 { //这个优先队列每次找到最小的路弹出，然后更改dis中的值，相当于松弛操作 //所以只要做好标记，表明这个点已经判断过就好，dijk用的就是贪心思想，每次找到最小值进行松弛，优先队列刚好可以完成这个操作 //例如1 3 2，1 2 2，2 3 3，那么弹出的一定是1 3 2这组数据，所以1到3的对短路就是2 cur=que.top(); que.pop(); v=cur.v; if(vis[v]==1) continue; dis[v]=cur.w; vis[v]=1; for(int i=first[v]; i!=-1; i=e[i].next) { if(vis[e[i].v]==0) { nwnode=e[i]; nwnode.w+=cur.w; que.push(nwnode); } } } memset(vis,0,sizeof(vis)); while(!que.empty()) que.pop(); for(int i=first1[1]; i!=-1; i=e1[i].next) que.push(e1[i]); vis[1]=1; while(!que.empty())//这个是其他点到一号点 { cur=que.top(); que.pop(); if(vis[cur.u]==1) continue; dis1[cur.u]=cur.w; vis[cur.u]=1; for(int i=first1[cur.u]; i!=-1; i=e1[i].next) { if(vis[e1[i].u]==0) { nwnode=e1[i]; nwnode.w+=cur.w; que.push(nwnode); } } } long long sum=0; for(int i=2; i<=n; i++) sum+=dis[i]+dis1[i]; printf("%lld\n",sum); } return 0; }