解题思路:Dijsktra+堆优化
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 #include<cstring> 5 #define MAX 1100000 6 using namespace std; 7 int head[MAX],top; 8 int dis[MAX],vis[MAX]; 9 struct edge{ 10 int from; 11 int to; 12 int cost; 13 int next; 14 }e[MAX],save[MAX]; 15 void push_front(int from,int to,int cost) 16 { 17 top++; 18 e[top].from=from; 19 e[top].to=to; 20 e[top].cost=cost; 21 e[top].next=head[from]; 22 head[from]=top; 23 } 24 struct Node{ 25 int x; 26 int cost; 27 bool operator<(const Node &b)const 28 { 29 30 return b.cost<cost; 31 } 32 }temp,p,sta; 33 void bfs(int s) 34 { 35 sta.x=s; 36 sta.cost=0; 37 memset(vis,0,sizeof(vis)); 38 memset(dis,0,sizeof(dis)); 39 priority_queue<Node> que; 40 que.push(sta); 41 while(!que.empty()) 42 { 43 p=que.top(); 44 que.pop(); 45 if(!vis[p.x]) 46 { 47 vis[p.x]=1; 48 dis[p.x]=p.cost; 49 for(int i=head[p.x];i!=0;i=e[i].next) 50 { 51 temp.x=e[i].to; 52 if(!vis[temp.x]) 53 { 54 temp.cost=p.cost+e[i].cost; 55 que.push(temp); 56 57 } 58 } 59 } 60 } 61 // printf("%d ",dis[en]); 62 } 63 int main() 64 { 65 int t,q,n; 66 while(~scanf("%d",&t)) 67 { 68 while(t--) 69 { 70 71 scanf("%d%d",&n,&q); 72 for(int i=1; i<=q; i++) 73 { 74 int u,v,c; 75 scanf("%d%d%d",&u,&v,&c); 76 save[i].from=u,save[i].to=v,save[i].cost=c; 77 } 78 long long ans=0; 79 ///1 80 top=0; 81 memset(head,0,sizeof(head)); 82 for(int i=1;i<=q;i++) 83 push_front(save[i].from,save[i].to,save[i].cost); 84 bfs(1); 85 for(int i=1;i<=n;i++)ans+=dis[i]; 86 ///2 87 top=0; 88 memset(head,0,sizeof(head)); 89 for(int i=1;i<=q;i++) 90 push_front(save[i].to,save[i].from,save[i].cost); 91 bfs(1); 92 for(int i=1;i<=n;i++)ans+=dis[i]; 93 94 /// 95 printf("%lld ",ans); 96 97 98 } 99 100 } 101 return 0; 102 }