POJ 1797 Heavy Transportation / SCU 1819 Heavy Transportation (图论,最短路径)

时间:2022-08-24 20:25:09

POJ 1797 Heavy Transportation / SCU 1819 Heavy Transportation (图论,最短路径)

Description

Background

Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.

Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.

Problem

You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo's place) to crossing n (the customer's place). You may assume that there is at least one path. All streets can be travelled in both directions.

Input

The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line.

Sample Input

1

3 3

1 2 3

1 3 4

2 3 5

Sample Output

Scenario #1:

4

Http

POJ:https://vjudge.net/problem/POJ-1797

SCU:https://vjudge.net/problem/SCU-1819

Source

图论,最短路径

题目大意

求解两点之间所有路径中,最小权值最大的路径

解决思路

同样运用改进的spfa算法解决,顺带复习了一下Dijkstra算法

Dijkstra(250ms)略快于spfa(266ms)

请不要使用cin读入,并且注意输出格式

代码

spfa实现

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std; const int maxN=1001;
const int inf=2147483647; class Edge
{
public:
int v,w;
}; int n,m;
vector<Edge> E[maxN];
int Dist[maxN];
bool inqueue[maxN];
queue<int> Q; int main()
{
int T;
cin>>T;
for (int ti=1;ti<=T;ti++)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
E[i].clear();
for (int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
E[u].push_back((Edge){v,w});
E[v].push_back((Edge){u,w});
}
memset(Dist,0,sizeof(Dist));
memset(inqueue,0,sizeof(inqueue));
while (!Q.empty())
Q.pop();
inqueue[1]=1;
Q.push(1);
Dist[1]=inf;
do
{
int u=Q.front();
Q.pop();
inqueue[u]=0;
for (int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if (min(Dist[u],E[u][i].w)>Dist[v])
{
Dist[v]=min(Dist[u],E[u][i].w);
if (inqueue[v]==0)
{
Q.push(v);
inqueue[v]=1;
}
}
}
}
while (!Q.empty());
printf("Scenario #%d:\n%d\n\n",ti,Dist[n]);
}
return 0;
}

Dijkstra实现

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std; const int maxN=1001;
const int inf=2147483647; class Edge
{
public:
int v,w;
}; int n,m;
vector<Edge> E[maxN];
int Dist[maxN];
bool vis[maxN]; int main()
{
int T;
cin>>T;
for (int ti=1;ti<=T;ti++)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
E[i].clear();
for (int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w); E[u].push_back((Edge){v,w});
E[v].push_back((Edge){u,w});
}
memset(Dist,0,sizeof(Dist));
memset(vis,0,sizeof(vis));
Dist[1]=inf;
for (int i=1;i<n;i++)
{
int id,mx=-inf;
for (int j=1;j<=n;j++)
if ((Dist[j]>mx)&&(vis[j]==0))
{
mx=Dist[j];
id=j;
}
if (id==n)
break;
vis[id]=1;
for (int j=0;j<E[id].size();j++)
{
int v=E[id][j].v;
if ((vis[v]==0)&&(min(Dist[id],E[id][j].w)>Dist[v]))
{
Dist[v]=min(Dist[id],E[id][j].w);
}
}
}
printf("Scenario #%d:\n%d\n\n",ti,Dist[n]);
}
return 0;
}

POJ 1797 Heavy Transportation / SCU 1819 Heavy Transportation (图论,最短路径)的更多相关文章

  1. POJ 1797 &Tab;Heavy Transportation (Dijkstra变形)

    F - Heavy Transportation Time Limit:3000MS     Memory Limit:30000KB     64bit IO Format:%I64d & ...

  2. poj 1797 Heavy Transportation(最大生成树)

    poj 1797 Heavy Transportation Description Background Hugo Heavy is happy. After the breakdown of the ...

  3. POJ&period;1797 Heavy Transportation &lpar;Dijkstra变形&rpar;

    POJ.1797 Heavy Transportation (Dijkstra变形) 题意分析 给出n个点,m条边的城市网络,其中 x y d 代表由x到y(或由y到x)的公路所能承受的最大重量为d, ...

  4. POJ 1797 ——Heavy Transportation——————【最短路、Dijkstra、最短边最大化】

    Heavy Transportation Time Limit:3000MS     Memory Limit:30000KB     64bit IO Format:%I64d & %I64 ...

  5. Heavy Transportation POJ 1797 最短路变形

    Heavy Transportation POJ 1797 最短路变形 题意 原题链接 题意大体就是说在一个地图上,有n个城市,编号从1 2 3 ... n,m条路,每条路都有相应的承重能力,然后让你 ...

  6. POJ 1797 Heavy Transportation &lpar;最大生成树&rpar;

    题目链接:POJ 1797 Description Background Hugo Heavy is happy. After the breakdown of the Cargolifter pro ...

  7. POJ 1797 Heavy Transportation &lpar;Dijkstra&rpar;

    题目链接:POJ 1797 Description Background Hugo Heavy is happy. After the breakdown of the Cargolifter pro ...

  8. POJ 2502 Subway &sol; NBUT 1440 Subway &sol; SCU 2186 Subway(图论,最短距离)

    POJ 2502 Subway / NBUT 1440 Subway / SCU 2186 Subway(图论,最短距离) Description You have just moved from a ...

  9. POJ 1860 Currency Exchange &sol; ZOJ 1544 Currency Exchange (最短路径相关,spfa求环)

    POJ 1860 Currency Exchange / ZOJ 1544 Currency Exchange (最短路径相关,spfa求环) Description Several currency ...

随机推荐

  1. sublime Text3 插件编写教程&lowbar;第一课

    今天给大家分享一下编写一个Sublime Text3 插件的流程以及使用插件解决的一个实际问题. 一.开发插件的前提条件 开发sublime插件用到的是Python语言,因此必须懂Python语言的基 ...

  2. zz A list of open source C&plus;&plus; libraries

    A list of open source C++ libraries < cpp‎ | links http://en.cppreference.com/w/cpp/links/libs Th ...

  3. Spring MVC框架下在java代码中访问applicationContext&period;xml文件中配置的文件(可以用于读取配置文件内容)

    <bean id="propertyConfigurer" class="com.****.framework.core.SpringPropertiesUtil& ...

  4. storm 入门

    Storm的典型用例有哪些呢? 流处理:正如前面的例子中所展示的,和其他流处理系统不同的是,使用Storm不需要中间队列. 连续计算:向客户端持续发送数据,以便它们能实时更新.显示结果,例如网站统计. ...

  5. msyql判断记录是否存在的三种方法

    1. select count(*) from .... 这种方法最常见但是效率比较低,因为它需要扫描所有满足条件的记录 2. select 1 from xxxtable where .... 这种 ...

  6. Centos设置防火墙与开放访问端口

    一. jeuxs在启动后可能会出现启动jexus成功,但是访问失败.但是在服务器内部访问没问题. 列出所有端口 netstat -ntlp 查看已经开放的端口: firewall-cmd --list ...

  7. Python3 与 C&num; 面向对象之~异常相关

      周末多码文,昨天晚上一篇,今天再来一篇: 在线编程:https://mybinder.org/v2/gh/lotapp/BaseCode/master 在线预览:http://github.les ...

  8. aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

    证券代码 证券简称 大股东持股比例 [日期] 最新 [大股东排名] 第1名 [单位] % 总市值2 [交易日期] 最新收盘日 [单位] 亿元 000004.SZ 国农科技 28.4200 23.261 ...

  9. HDU 1078 FatMouse and Cheese &lpar; DP&comma; DFS&rpar;

    HDU 1078 FatMouse and Cheese ( DP, DFS) 题目大意 给定一个 n * n 的矩阵, 矩阵的每个格子里都有一个值. 每次水平或垂直可以走 [1, k] 步, 从 ( ...

  10. JavaScript词法作用域与调用对象

    关于 Javascript 的函数作用域.调用对象和闭包之间的关系很微妙,关于它们的文章已经有很多,但不知道为什么很多新手都难以理解.我就尝试用比较通俗的语言来表达我自己的理解吧. 作用域 Scope ...