HDU2066 一个人的旅行(Dijkstra)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2066

思路：以0为起点，到草儿周围的车站建边，距离为0，其他的正常建立双向边，跑dijstra选出最小距离。

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 20000;
const int INF=1<<30;
int d[maxn],vis[maxn];
struct edge
{
	int to,w;
};
struct node
{
	int x,d;
	bool operator < (const node &b)const
	{
		return d>b.d;
	}
};
vector<edge> g[maxn];
void dijstra(int s,int n)
{
	priority_queue<node> q;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++)d[i]=INF;
	d[s]=0;
	q.push(node{s,d[s]});
	while(!q.empty())
	{
		node t=q.top();q.pop();
		int u=t.x;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].to;
			int w=g[u][i].w;
			if(d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				q.push(node{v,d[v]});
			}
		}
	}
}
int main()
{
	int n,m,k;
	int N=-1;
//	freopen("in.txt","r",stdin);
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		for(int i=0;i<=N;i++)g[i].clear();
		N=-1;
		for(int i=1;i<=n;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			g[u].push_back(edge{v,w});
			g[v].push_back(edge{u,w});
			if(N<u)N=u;
			if(N<v)N=v;
		}
		for(int i=0;i<m;i++)
		{
			int s;
			scanf("%d",&s);
			g[0].push_back(edge{s,0});
			g[s].push_back(edge{0,0});
		}
		dijstra(0,N);
		int ans=1<<30;
		for(int i=0;i<k;i++)
		{
			int temp;
			scanf("%d",&temp);
			if(d[temp]<ans)ans=d[temp];
		}
		printf("%d\n",ans);
	}
}