【杭电oj】2066 - 一个人的旅行（迪杰斯塔拉，优先队列优化）

   6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

   9

#include <cstdio>
#include <queue>
#include <algorithm>
#define MAX 1000
using namespace std;
struct node
{
	int now,dis;
	bool friend operator < (node a, node b)
	{
		return a.dis > b.dis;
	}
}t,ne;
int d[MAX+22];
int map[MAX+11][MAX+11];
bool used[MAX+11];
int maxx;
priority_queue<node> q;

void init()
{
	while (!q.empty())
		q.pop();
	for (int i = 0 ; i <= MAX ; i++)
	{
		used[i] = false;
		d[i] = 999999;
		for (int j = i ; j <= MAX ; j++)
			map[i][j] = map[j][i] = 999999;
	}
}
void Dijkstra()
{
	d[0] = 0;
	used[0] = true;
	for (int i = 1 ; i <= maxx ; i++)
	{
		if (map[0][i] == 0)
		{
			t.now = i;
			t.dis = 0;
			q.push(t);
			d[i] = 0;
		}
	}
	while (!q.empty())
	{
		t = q.top();
		q.pop();
		if (used[t.now])
			continue;
		used[t.now] = true;
		for (int i = 1 ; i <= maxx ; i++)
		{
			if ((map[i][t.now] != 999999) && d[i] > (d[t.now] + map[i][t.now]))
			{
				ne.now = i;
				ne.dis = d[t.now] + map[i][t.now];
				q.push(ne);
				d[i] = d[t.now] + map[i][t.now];
			}
		}
	}
}
int main()
{
	int T,S,D;
	int ans;
	while (~scanf ("%d %d %d",&T,&S,&D))
	{
		init();
		maxx = 0;
		while (T--)
		{
			int x,y,z;
			scanf ("%d %d %d",&x,&y,&z);
			if (map[x][y] > z)		//判断重边 
				map[x][y] = map[y][x] = z;
			maxx = max (maxx , x);
			maxx = max (maxx , y);
		}
		while (S--)
		{
			int x;
			scanf ("%d",&x);
			map[0][x] = map[x][0] = 0;
		}
		Dijkstra();
		ans = 999999;
		while (D--)
		{
			int x;
			scanf ("%d",&x);
			ans = min (ans , d[x]);
		}
		printf ("%d\n",ans);
	}
	return 0;
}