Heavy Transportation POJ 1797 最短路变形

题意

题意大体就是说在一个地图上，有n个城市，编号从1 2 3 ... n，m条路，每条路都有相应的承重能力，然后让你求从编号为1的城市到编号为n的城市的路线中，最大能经过多重的车。

解题思路

这个题可以使用最短路的思路，不过转移方程变了\(dis[j]=max(dis[j], min(dis[u], e[u][j]))\)。这里dis[j]表示从标号为1的点到达编号为j的点的路径中，最小的承重能力，就像短板效应样，一个木桶所能容纳的水是由最短的木板决定的。

代码实现

//使用优先队列优化的Dijkstra算法

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

const int maxn=1e3+7;

const int inf=0x3f3f3f3f;

struct edge{

	int to, cost;

};

struct node{

	int d, u;

	friend bool operator<(const node a, const node b){

		return  a.d < b.d;

	}

};

int dis[maxn];

bool vis[maxn];

vector<edge> g[maxn];

priority_queue<node> que;

int t, n, m;

void init()

{

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

		g[i].clear();

		vis[i]=0;

		dis[i]=-inf;

	}

	while(!que.empty()) que.pop();

}

void dij(int s)

{

	int u, num=0;

	edge e;

	dis[s]=inf;

	node tmp={inf, s}, next;

	que.push(tmp);

	while(!que.empty() && num<=n)

	{

		tmp=que.top();

		que.pop();

		u=tmp.u;

		if(vis[u]) continue;

		vis[u]=1;

		num++;

		for(int i=0; i<g[u].size(); i++)

		{

			e=g[u][i];

			if(!vis[e.to] && dis[e.to] < min(dis[u], e.cost) )

			{

				dis[e.to]=min(dis[u], e.cost);

				next.d=dis[e.to];

				next.u=e.to;

				que.push(next);

			}

		}

	}

}

int main()

{

	int cnt=1;

	scanf("%d",&t);

	while(t--)

	{

		int u, v;

		edge e;

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

		init();

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

		{

			scanf("%d%d%d", &u, &v, &e.cost);

			e.to=v;

			g[u].push_back(e);

			e.to=u;

			g[v].push_back(e);

		}

		dij(1);

		printf("Scenario #%d:\n", cnt++);

		printf("%d\n\n", dis[n]);

	}

	return 0;

}

巴特西

Heavy Transportation POJ 1797 最短路变形

Heavy Transportation POJ 1797 最短路变形

题意

解题思路

代码实现

最新文章

热门文章