2692682_ac_539ms_4020k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>
#define MAX 30001
#define INF 2100000000
#define INIT (Node *)malloc(sizeof(Node))
using namespace std;

typedef struct node
{
	int id, w;
	struct node *next;
}Node;

struct NODE
{
	Node *head;
}graph[MAX];

int n, m;
int heap[MAX], dis[MAX];

void read_map()
{
	int i;
	int a, b, c;

	scanf("%d%d",&n,&m);
	for(i = 0; i < n; i++)
	{
		graph[i].head = INIT;
		graph[i].head->next = NULL;
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		if(a==b)
			continue;
		a--,b--;
		Node *p;
		p = INIT;
		p->w = c;p->id = a;
		p->next = graph[b].head->next;
		graph[b].head->next = p;
	}
}

bool cmp(int a,int b)
{
	return dis[a]>dis[b];
}

void dijkstra(int s,int t)
{
	int i, u, r;
	int mark[MAX];

	for(i = 0; i < n; i++)
		dis[i] = INF;
	r = 0;
	heap[r] = s;
	dis[s] = 0;
	r++;
	memset(mark,0,sizeof(mark));
	while(!mark[t])
	{
		u = heap[0];
		pop_heap(heap,heap+r,cmp);
		r--;
		if(mark[u])
			continue;
		mark[u] = 1;
		Node *p;
		p = graph[u].head;
		while (p->next)
		{
			if(!mark[p->next->id]&&dis[u]+p->next->w<dis[p->next->id])
			{
				dis[p->next->id] = dis[u] + p->next->w;
				heap[r] = p->next->id;
				r++;
				push_heap(heap,heap+r,cmp);
			}
			p = p->next;
		}
	}
	printf("%d\n",dis[t]);
}


int main()
{
	read_map();
	dijkstra(n-1,0);
	return 0;
}