Source Code

• Source Code

  #include<cstdio>
  
  #define MAXINT	(((long long)1)<<60)
  #define SWAP(x, y) do{ if((x)!=(y)){(x)^=(y); (y)^=(x); (x)^=(y);}}while(0);
  #define	MAXM	1000001
  #define MAXN	1000001
  
  struct Edg{
  	int n;
  	int p;
  	int next;
  }EE[MAXM<<2];
  
  int head1[MAXN];
  int head2[MAXN];
  long long dist[MAXN];
  long long ans;
  int top;
  int n;
  int m;
  
  long long heap[MAXN];
  int heap_size;
  int id[MAXN];
  
  void swim(int u){
  	int parent = u >> 1;
  	while(parent > 0){
  		if(dist[heap[u]] < dist[heap[parent]]){
  			SWAP(id[heap[parent]], id[heap[u]]);
  			SWAP(heap[parent], heap[u]);
  			u = parent;
  			parent = u >> 1;
  		}
  		else{
  			break;
  		}
  	}
  }
  
  void sink(int u){
  	int child = u << 1;
  	while(child < heap_size){
  		if(child + 1 < heap_size && dist[heap[child]] < dist[heap[child + 1]]){
  			child++;
  		}
  		if(dist[heap[child]] < dist[heap[u]]){
  			SWAP(id[heap[child]], id[heap[u]]);
  			SWAP(heap[child], heap[u]);
  			u = child;
  			child = u << 1;
  		}
  		else{
  			break;
  		}
  	}
  }
  
  int getMin(){
  	int reVal = -1;
  	if(heap_size > 1){
  		reVal = heap[1];
  		heap_size--;
  		if(heap_size > 1){
  			SWAP(id[heap[1]], id[heap[heap_size]]);
  			SWAP(heap[1], heap[heap_size]);
  			sink(1);
  		}
  	}
  	return reVal;
  }
  
  inline int nextInt(){
  	char ch = getchar();
  	int x = 0;
  	while(ch < '0' || ch > '9'){
  		ch = getchar();
  	}
  	while(ch >= '0' && ch <= '9'){
  		x = x * 10 + ch - 48;
  		ch = getchar();
  	}
  	return x;
  }
  
  void dij(int* head){
  	int i = 0;
  	int minP = 0;
  	int I = 0;
  	for(i = 1; i <= n; i++){
  		dist[i] = MAXINT;
  		heap[i] = i;
  		id[i] = i;
  	}
  	dist[1] = 0;
  	heap_size = n + 1;
  	while((I = getMin()) != -1){
  		minP = dist[I];
  		i = head[I];
  		while(i != -1){
  			I = EE[i].n;
  			if(minP + EE[i].p < dist[I]){
  				dist[I] = minP + EE[i].p;
  				swim(id[I]);
  			}
  			i = EE[i].next;
  		}
  	}
  	for(i = 1; i <= n; i++){
  		ans += dist[i];
  	}
  }
  
  void buildEdg(int I, int J, int p, int* head){
  	EE[top].n = J;
  	EE[top].p = p;
  	EE[top].next = head[I];
  	head[I] = top++;
  }
  
  int main(int argc, char* argv[], char* env[])
  {
  	int i = 0;
  	int I = 0;
  	int J = 0;
  	int P = 0;
  	int caseNum = 0;
  	while(scanf("%d", &caseNum) != EOF){
  		while(caseNum-- > 0){
  			n = nextInt();
  			m = nextInt();
  			top = 0;
  			for(i = 1; i <= n; i++){
  				head1[i] = head2[i] = -1;
  			}
  			while(m-- > 0){
  				I = nextInt();	
  				J = nextInt();
  				P = nextInt();
  				buildEdg(I, J, P, head1);
  				buildEdg(J, I, P, head2);
  			}
  			ans = 0;
  			dij(head1);
  			dij(head2);
  			printf("%lld\n", ans);
  		}
  	}
  	return 0;
  }
  

Source Code

• Source Code

  #include<cstdio>
  
  #define MAXINT	(((long long)1)<<60)
  #define	MAXM	1000001
  #define MAXN	1000001
  
  struct Edg{
  	int n;
  	int p;
  	int next;
  }EE[MAXM<<2];
  
  int head1[MAXN];
  int head2[MAXN];
  long long dist[MAXN];
  int spfa_que[MAXN];
  int mark[MAXN];
  long long ans;
  int top;
  int spfa_que_head;
  int spfa_que_tail;
  int n;
  int m;
  
  inline int nextInt(){
  	char ch = getchar();
  	int x = 0;
  	while(ch < '0' || ch > '9'){
  		ch = getchar();
  	}
  	while(ch >= '0' && ch <= '9'){
  		x = x * 10 + ch - 48;
  		ch = getchar();
  	}
  	return x;
  }
  
  inline void buildEdg(int I, int J, int p, int* head){
  	EE[top].n = J;
  	EE[top].p = p;
  	EE[top].next = head[I];
  	head[I] = top++;
  }
  
  void spfa_slf(int* head){
  	int i = 0;
  	int I = 0;
  	int q = 0;
          int t = 0;
  	for(i = 1; i <= n; i++){
  		dist[i] = MAXINT;
  		mark[i] = 0;
  	}
  	dist[1] = 0;
  	spfa_que_head = 0;
  	spfa_que_tail = 0;
  	spfa_que[spfa_que_head++] = 1;
  	mark[1] = 1;
  	do{
  		spfa_que_head--;
  		if(spfa_que_head < 0){
  			spfa_que_head = n - 1;
  		}
  		I = spfa_que[spfa_que_head];
  		mark[I] = 0;
  		q = head[I];
  		while(q != -1){
  			i = EE[q].n;
  			if(dist[I] + EE[q].p < dist[i]){
  				dist[i] = dist[I] + EE[q].p;
  				if(!mark[i]){
  					mark[i] = 1;
                                          t = spfa_que_head - 1;
                                          if(t < 0)t = n - 1;
  					if(spfa_que_head != spfa_que_tail 
  						&& dist[i] < dist[spfa_que[t]]){
  						spfa_que[spfa_que_head++] = i;
  						if(spfa_que_head >= n){
  							spfa_que_head = 0;
  						}
  					}
  					else{
  						spfa_que_tail--;
  						if(spfa_que_tail < 0){
  							spfa_que_tail = n - 1;
  						}
  						spfa_que[spfa_que_tail] = i;
  					}
  				}
  			}
  			q = EE[q].next;
  		}
  	}while(spfa_que_head != spfa_que_tail);
  	for(i = 1; i <= n; i++){
  		ans += dist[i];
  	}
  }
  
  int main(int argc, char* argv[], char* env[])
  {
  	int i = 0;
  	int I = 0;
  	int J = 0;
  	int P = 0;
  	int caseNum = 0;
  	while(scanf("%d", &caseNum) != EOF){
  		while(caseNum-- > 0){
  			n = nextInt();
  			m = nextInt();
  			top = 0;
  			for(i = 1; i <= n; i++){
  				head1[i] = head2[i] = -1;
  			}
  			while(m-- > 0){
  				I = nextInt();	
  				J = nextInt();
  				P = nextInt();
  				buildEdg(I, J, P, head1);
  				buildEdg(J, I, P, head2);
  			}
  			ans = 0;
  			spfa_slf(head1);
  			spfa_slf(head2);
  			printf("%lld\n", ans);
  		}
  	}
  	return 0;
  }