dij.cpp

acm 常用算法和代码库

#include <stdio.h>
#include <iostream>
using namespace std;
const int SIZE= 1000001, MAXX=2000000;
int n,m,tail, dist[SIZE];
bool mark[SIZE];

struct Node
{
	int id, val;
	Node* next;
}node[SIZE];
struct Heap{
	int id, val;
}heap[2*SIZE];

int prev[SIZE];
void insert(int a, int b, int val)
{
	Node* p = new Node;
	p->id = a;
	p->val = val;
	p->next = node[b].next;
	node[b].next = p;	
}
void heappush(int id, int val)
{
	heap[++tail].id = id;
	heap[tail].val = val;
	int child, parent, temp;
	child = tail;
	while((parent = child/2)>=1)
	{
		if(heap[child].val < heap[parent].val)
		{
			temp = heap[child].id;
			heap[child].id = heap[parent].id;
			heap[parent].id = temp;
			
			temp = heap[child].val;
			heap[child].val = heap[parent].val;
			heap[parent].val = temp;
			child = parent;
		}
		else
			break;
	}
}
int heappop()
{
	int child, parent, temp,ret;
	ret = heap[1].id;
	heap[1].id = heap[tail].id; 
	heap[1].val = heap[tail--].val; 
	parent = 1;
	while((child=2*parent)<=tail)
	{
		if(child+1<=tail && heap[child+1].val < heap[child].val)
			child++;
		if(heap[child].val<heap[parent].val)
		{
			temp = heap[child].id;
			heap[child].id = heap[parent].id;
			heap[parent].id = temp;
			
			temp = heap[child].val;
			heap[child].val = heap[parent].val;
			heap[parent].val = temp;
			parent = child;
		}
		else break;			
	}
	return ret;
}
int dijkstra(int s, int t)
{
	int i;
	for(i=1; i<=n; i++)
	{
		dist[i] = MAXX;
		mark[i] = false;
	}
	Node* p;
	p = node[s].next;
	while(p)
	{
		dist[p->id] = p->val;
		heappush(p->id, p->val);
		p = p->next;
	}
	mark[s] = true; dist[s] = 0;

	for(i=1; i<n; i++)
	{
		int pop = heappop();
		while(mark[pop])
			pop = heappop();
			
			int k;
		do    //清空队列
		{
			  k=heappop();
		}while(k!=0);
		
		if(pop ==t || dist[pop]==MAXX)	break;
		mark[pop] = true;
		p = node[pop].next;
		while(p)
		{
			if(!mark[p->id]&&(dist[p->id]==MAXX || dist[pop]+p->val< dist[p->id]))
			{
				dist[p->id] = dist[pop] + p->val;
				prev[p->id]= pop;
				heappush(p->id, dist[p->id]);
			}
			p = p->next;
		}
	}
	return (dist[t]>=MAXX)?(-1):(dist[t]);
}

void init(int n)
{
	int i;
     for(  i=1;i<=n;i++)
     {
             node[i].id=0;
             node[i].next=NULL;
             node[i].val=MAXX;
     }
     for(  i=1;i<=2*n;i++)
     {
             heap[i].id=0;      
             heap[i].val=MAXX;
     }
     for(  i=1;i<=n;i++)
     {
             mark[i]=0;
     }
     
     
}
 
int main()
{
    
	int i,j;
    	
	while(cin>>n>>m){
        init(n);
    	for(int i=0;i<m;i++)
    	{
    		int s,d,dis;
    		cin>>s>>d>>dis;
    		insert(s,d,dis);
    		insert(d,s,dis);
     	}
     	int start,end;
     	 
     	cout<<dijkstra(1,n)<<endl;;
   }
   //insert(i,j,dist);

}