BNU 20950 ——沉重的货物 —————— · 最短路、最短边最大化」

沉重的货物

Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

Submit Status Statistics Discuss

CUITCPC是一个专门生产大型货运火车的工厂。他们的新型货运火车XX V1.0，是如此之大，以至于可以运输的货物的重量并不取决于那个火车本身，而只是受限于你所通过的铁路的承重。

给你出发和目标城市，你的任务就是求出火车从初始城市到目标城市的最大载重。

Input

输入可能包括一组或者多组测试数据。每一个测试数据的前两行是两个整数:城市的数量n(2<=n<=1000)和铁路的条数r(1<=r<= 19900)。

紧接着是r行，每一行描述一条连接两个城市的铁路以及这段铁路所能承受的最大重量。城市名不会超过30个字符，也不会有空白字符出现在城市名中。承重是一个0-10000的整数。铁路都是双向的。

最后一行是两个城市的名字：初始城市和目标城市。

输入的结束条件是n和r都为0

Output

对于每一组测试数据

输出包括3行：

l 一行输出"Scenario #x"，其中x是测试数据的组数

l 一行输出"y tons"，其中y表示最大载重量

l 一个空行

Sample Input

4 3
ACM ICPC 100
ICPC World 80
World CPC 120
ACM CPC
5 5
ACM ICPC 100
ICPC World 80
World CPC 120
ACM Chengdu 220
Chengdu CPC 170
CPC ACM
0 0

Sample Output

Scenario #1
80 tons

Scenario #2
170 tons

Source

首届成都信息工程学院程序设计竞赛决赛

解题思路：将d[i]表示成从原点到i点所有路径中最短边的最大值。只需要改变dijstra中的判断条件改一下，初始化改一下就行了。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int maxn = 1e3 + 300;
const LL INF = 0x3f3f3f3f;
map<string,int>mp;
struct Node{
	    int d;
		int u;
		Node(){}	
		Node(int _d,int _u):d(_d),u(_u){}		
		bool operator < (const Node & rhs)const{
			return d < rhs.d;
		}
};
priority_queue<Node>PQ;
struct Edge{
	    int from, to, next, dist;
		    Edge(){}
			    Edge(int _from,int _to,int _next,int _dist):from(_from),to(_to),next(_next),dist(_dist){}
}edges[maxn*100];
int tot, head[maxn];
void init(){    
	tot = 0;
	memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int d){
	edges[tot] = Edge(u,v,head[u],d);
	head[u] = tot++;
}
int st, en, n;
int d[maxn], vis[maxn];
void Dijstra(){
	    for(int i = 1; i <= n; i++){
			d[i] = 0;
	    }
		memset(vis,0,sizeof(vis));
		d[st] = INF;
		while(!PQ.empty()){
			Node x = PQ.top();
			PQ.pop();
			int u = x.u;
			if(vis[u]) continue;
			vis[u] = 1;		
			for(int i = head[u]; i != -1; i = edges[i].next){
				Edge &e = edges[i];
				if(!vis[e.to] && d[e.to] < min(d[e.from], e.dist)){
					d[e.to] = min(d[e.from], e.dist);
					PQ.push(Node(d[e.to],e.to));
				}	
			}
		}
}
int main(){
	    string s1,s2;
		int m, dis, T = 0;
		while(scanf("%d%d",&n,&m)!=EOF&& n&&m){
			int nn = 0;
			init();
			mp.clear();
//			mp.erase(mp.begin(),mp.end());
			for(int i = 1; i <= m; i++){
				cin>>s1>>s2;
				cin>>dis;
				if(mp.count(s1) == 0){
					mp[s1] = ++nn;
				}
				if(mp.count(s2) == 0){
					mp[s2] = ++nn;
				}
				addedge(mp[s1],mp[s2],dis);
				addedge(mp[s2],mp[s1],dis);
			}
			cin>>s1 >> s2;
			st = mp[s1]; en = mp[s2];
			PQ.push(Node(INF,st));
			Dijstra();
			cout<<"Scenario #"<<++T<<endl;
			cout<<d[en] <<" tons"<<endl<<endl;
		}
		return 0;
}