HDU 2680 shortest path Dijkstra + chained forward star + priority queue (template)

sketch ：

It is more convenient to build a map in reverse , Finally, compare the path from the end point to the starting point , Choose the shortest one , Is the answer .

  subject ：http://acm.hdu.edu.cn/showproblem.php?pid=2680

  Code ：

#include <iostream>
#include <queue>
#include <vector>
#define MAX 0x3f3f3f3f
const int maxn = 2e4+10;
using namespace std;
struct Edge{
	int to,dis,next;
};
Edge e[maxn];
int head[maxn],dis[maxn],cnt;
int vis[maxn];
void add_Edge(int u,int v,int d) {
	e[cnt].dis = d; //  distance  
	e[cnt].to = v;//  End  
	e[cnt].next = head[u];
	head[u] = cnt++;
}
struct Node{
	int dis,pos;// dis For the shortest distance ,pos Is number  . 
	bool operator <(const Node &x) const {
		return x.dis < dis; //  Heap ,   x.dis > dis  Big root pile  
	}
}; 

priority_queue <Node> Q;

void Dijkstra(int s) {
	dis[s] = 0;
	Q.push((Node){0,s});
	while(!Q.empty()) {
		Node temp = Q.top();
		Q.pop();
		int x = temp.pos,d = temp.dis; 
		if(vis[x]) continue;
		vis[x] = 1;
		for(int i = head[x]; ~i; i = e[i].next) {
			int y = e[i].to;
			if(!vis[y] && dis[y] > dis[x] + e[i].dis) {
				dis[y] = dis[x] + e[i].dis;
				Q.push((Node){dis[y],y});
			}
		}
	}
	while(!Q.empty()) Q.pop();
}

int main() {
	int n,m,s,a,b,v,t;
	while(~scanf("%d%d%d",&n,&m,&s)) {
		for(int i = 0; i <= n; i++) {
			dis[i] = MAX;
			vis[i] = 0;
			head[i] = -1;
		}
		cnt = 0;
		for(int i = 1; i <= m; i++) {
			scanf("%d%d%d",&a,&b,&v);
			add_Edge(b,a,v);//  Reverse construction . 
		}
		Dijkstra(s);
		scanf("%d",&t);
		int ans = MAX;
		for(int i = 1; i <= t; i++) {
			scanf("%d",&a);
			ans = min(ans,dis[a]);
		}
		if(ans == MAX) printf(N"-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}