POJ 2457 Part Acquisition(最短路）

題目連接配接：http://poj.org/problem?id=2457

裸露的最短路，Dijkstra + 優先隊列水過。。。

題意：就是求1到k之間的最短路，每條邊的權值為1，若存在最短路，輸出任意一條，若不存在，輸出-1。

代碼如下：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

#define INS 1<<29
#define N 1005  //頂點的個數
#define SIZE 50005 //邊的個數
#define CLR(arr,v) memset(arr,v,sizeof(arr))

class short_path{
public:
	short_path(){}
	void init(int m,int n){
		num_ed = m;num_v = n;
		CLR(des,0);CLR(next,0); CLR(h,0);
		for(int i = 0;i < N;++i)
			dis[i] = INS;
		while(!q.empty()) q.pop();
	}
	void add(int u,int v,int f){
		des[++pos] = v;
		val[pos] = f;
		next[pos] = h[u];
		h[u] = pos;
	}
	int Dijkstra(int start,int end,int *root){
		dis[start] = 0;
		mid.d = start;
		mid.v = 0;
		q.push(mid);
		while(!q.empty()){
			int s = q.top().d,v = q.top().v;
			q.pop();
			for(int i = h[s]; i ;i = next[i]){
				if(dis[s] + val[i] < dis[ des[i] ]){
					root[ des[i] ] = s;
					dis[ des[i] ] = dis[s] + val[i];
					mid.d = des[i];
					mid.v = dis[ des[i] ];
					q.push(mid);
				}
			}
		}
		return dis[end] == INS?-1:dis[end];
	}
private:
	int h[N],dis[N],des[SIZE],next[SIZE],val[SIZE];
	int pos,num_ed,num_v,res;
	struct Edge{
		int d,v;
		bool operator<(const Edge &ed) const{
			return v > ed.v;
		}
	};
	struct Edge mid;
	priority_queue<Edge> q;
};
class short_path sp;

int root[N];

void dfs(int e){
	if(e == 1){
		printf("%d\n",e);
		return ;
	}
	dfs(root[e]);
	printf("%d\n",e);
}
int main()
{
	int n,k;
	while(~scanf("%d%d",&n,&k)){
		sp.init(n,k);
		int u,v;
		for(int i = 0;i < n;++i){
			scanf("%d%d",&u,&v);
			sp.add(u,v,1);
		}
		int minres = sp.Dijkstra(1,k,root);
		if(minres == -1) printf("-1\n");
		else{
			printf("%d\n",minres + 1);
			dfs(k);
		}
	}
	return 0;
}