poj_3159 最短路

题目大意

有N个孩子（N<=3000)分糖果。有M个关系(M<=150,000)。每个关系形如：A B C 表示第B个学生比第A个学生多分到的糖果数目，不能超过C。求第N个学生最多比第1个学生能多分几个糖果

题目分析

题目求第N个学生可以比第1个学生多分糖果数目，假设有从第1个同学经过一系列关系，可以到达第N个同学，比如存在路径1 1--->i1--->i2--->....ik--->N，表示同学i1比同学1最多多x1个糖果，同学i2比同学i1最多多x2个糖果....同学N比同学ik最多多xk+1个糖果; 还存在路径2 1--->j1-->j2.....-->jk--->N，表示同学j1比同学1最多多y1个糖果，同学j2比同学j1最多多y2个糖果....同学N比同学jk最多多jk+1个糖果...还存在路径3,4,5...
将各个同学视为图上的点，同学甲比乙最多多的糖果数视为甲到乙的边的长度。那么显然，同学N比同学1最多多的糖果数目为从1到N的最短路径，若大于最短路径，则观察从1到N的最短路径上经过的点，其中至少有相邻两点不满足要求（其中一个比另一个最多多x个糖果）。
题目转化为一个无负权边的无向图的单源最短路径问题，采用dijkstra算法解决。由于N^2 >> M，这是一个稀疏图，采用邻接矩阵存储。

题目实现(c++)

#include<stdio.h>

#include<string.h>

#include<vector>

#include<queue>

using namespace std;

#define MAX_NODE 30005

#define INFINITE 1 << 30

struct Edge{

	int vertex;			//该边连接的下一个顶点

	int dist;			//边的长度

	Edge(int v, int d) :

		vertex(v), dist(d){};

};

vector<vector<Edge> >gGraph; //存放图

bool gUsed[MAX_NODE];	//判断点v是否已经获得从原点s到该点的最短距离

int gDist[MAX_NODE];	//存放原点s到该点的当前最短距离

struct Compare{	//用于优先队列的比较

	bool operator()(const Edge& a, const Edge& b){

		return a.dist > b.dist;

	}

};

//注意，使用优先队列、set、map等结构时，注意合理的选择存放的元素，不要在push，pop的时候，改变已经存在于

//容器中的元素发生改变（因为要保证顺序性）

int Dijkstra(int s, int d, int n){

	memset(gUsed, false, sizeof(gUsed));

	priority_queue<Edge, vector<Edge>, Compare> pq;

	for (int i = 1; i <= n; i++)

		gDist[i] = INFINITE;

	gDist[s] = 0;

	Edge e(s, 0);

	pq.push(e);

	while (!pq.empty()){

		e = pq.top();

		pq.pop();

		if (gUsed[e.vertex])	//如果已经确定了从原点到该点的最短距离，则肯定也已经通过该点更新过了

								//其他邻接点的最短距离，则之后再从队列中取出该点，直接跳过

			continue;

		gUsed[e.vertex] = true;

		if (e.vertex == d){

			break;

		}

		for (int i = 0; i < gGraph[e.vertex].size(); i++){

			Edge& next_e = gGraph[e.vertex][i];

			if (!gUsed[next_e.vertex]){

				if (gDist[next_e.vertex] > gDist[e.vertex] + e.dist){

					gDist[next_e.vertex] = gDist[e.vertex] + e.dist;		//更新邻接点，并放入队列

					pq.push(Edge(next_e.vertex, gDist[next_e.vertex]));

				}

			}

		}

	}

	return gDist[d];

}

int main(){

	int n, m, u, v, c;

	scanf("%d %d", &n, &m);

	gGraph.resize(n + 1);

	for (int i = 0; i < m; i++){

		scanf("%d %d %d", &u, &v, &c);

		gGraph[u].push_back(Edge(v, c));

	}

	int result = Dijkstra(1, n, n);

	printf("%d\n", result);

	return 0;

}

巴特西

poj_3159 最短路

题目大意

题目分析

题目实现(c++)

最新文章

热门文章