文档章节

sicily 1031 Campus

Ciel
 Ciel
发布于 2012/12/16 18:02
字数 684
阅读 104
收藏 0

Description

At present, Zhongshan University has 4 campuses with a total area of 6.17 square kilometers sitting respectively on both sides of the Pearl River or facing the South China Sea. The Guangzhou South Campus covers an area of 1.17 square kilometers, the North Campus covers an area of 0.39 square kilometers, the Guangzhou East Campus has an area of 1.13 square kilometers and the Zhuhai Campus covers an area of 3.48 square kilometers. All campuses have exuberance of green trees, abundance of lawns and beautiful sceneries, and are ideal for molding the temperaments, studying and doing research.

Sometime, the professors and students have to go from one place to another place in one campus or between campuses. They want to find the shortest path between their source place S and target place T. Can you help them?

Input

The first line of the input is a positive integer C. C is the number of test cases followed. In each test case, the first line is a positive integer N (0<N<=100) that represents the number of roads. After that, N lines follow. The i-th(1<=i<=N) line contains two strings Si, Ti and one integer Di (0<=Di<=100). It means that there is a road whose length is Di between Si and Ti. Finally, there are two strings S and T, you have to find the shortest path between S and T. S, T, Si(1<=i<=N) and Ti(1<=i<=N) are all given in the following format: str_Campus.str_Place. str_Campus represents the name of the campus, and str_Place represents the place in str_Campus. str_Campus is "North", "South", "East" or "Zhuhai". str_Place is a string which has less than one hundred lowercase characters from "a-z". You can assume that there is at most one road directly between any two places.

Output

The output of the program should consist of C lines, one line for each test case. For each test case, the output is a single line containing one integer. If there is a path between S and T, output the length of the shortest path between them. Otherwise just output "-1" (without quotation mark). No redundant spaces are needed.

Sample Input

1
2
South.xiaolitang South.xiongdelong 2
South.xiongdelong Zhuhai.liyuan 100
South.xiongdelong South.xiaolitang

Sample Output

2

分析:

直接用Dijkstra算法,需要注意可能出现输入数据中两端点相等的情况,要加上特殊的判断(比较坑爹)。

代码:

// Problem#: 1031
// Submission#: 1789656
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <string>
#include <cstring>
#include <map>
using namespace std;

#define MAX 210
#define INF 1000000

int buffer[MAX][MAX];
int len[MAX];
bool judge[MAX];

int dijkstra( int b, int e, int n ){
	memset(judge,0,sizeof(judge));
	for( int i=0 ; i<n ; i++ )
		len[i] = INF;
	len[b] = 0;
	for( int i=0 ; i<n ; i++ ){
		int min = INF;
		int v = b;
		for( int j=0 ; j<n ; j++ )
			if( !judge[j] && len[j]<min ){
				min = len[j];
				v = j;
			}
		judge[v] = true;
		for( int j=0 ; j<n ; j++ )
			if( !judge[j] && len[v]+buffer[v][j]<len[j] )
				len[j] = len[v]+buffer[v][j];
	}
	if( judge[e]) return len[e];
	else return -1;
}

int main(){
	int c,n,l;
	string b,e;
	cin >> c;
	while( c-- ){
		cin >> n;
		map<string,int> sysu;
		int num = 0;
		for( int i=0 ; i<MAX ; i++ )
			for( int j=0 ; j<MAX ; j++ )
				buffer[i][j] = (i==j?0:INF);
		for( int i=0 ; i<n ; i++ ){
			cin >> b >> e >> l;
			if( !sysu.count(b) ) sysu[b] = num++;
			if( !sysu.count(e) ) sysu[e] = num++;
			buffer[sysu[b]][sysu[e]] = buffer[sysu[e]][sysu[b]] = l;
		}
		cin >> b >> e;
		if( b==e ) cout << 0 << endl;
		else if( !sysu.count(b) || !sysu.count(e) ) cout << -1 << endl;
		else cout << dijkstra(sysu[b],sysu[e],num) << endl;
	}
    return 0;
}

© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
Eclipse Memory Analyzer tool 工具的使用

1、前言 在使用阿里云的OSS服务时,服务器内存高居不下,导致服务异常,最终通过Jmap+MAT找到了内存溢出的方法,定位到了问题所在。 整体思路是先用Jmap从生产上dump下来内存快照,然后用Mat...

freeli
2017/10/31
1K
1
好用的开源二进制编辑器--NotePad++

访问地址http://notepad-plus-plus.org/ ![在此输入图片描述][1] [1]: http://static.oschina.net/uploads/space/2013/1031/210441_LClS_996206.gif...

清水湾2012
2013/10/31
2K
1
sicily 1150 简单魔板 sicily 1151 魔板 sicily 1515 魔板C

这三道题目大体相同,只是数据处理方式不同,需要修改的地方很少,因此只以1150为例说明即可。 Description 魔板由8个大小相同方块组成,分别用涂上不同颜色,用1到8的数字表示。 其初始状态...

Ciel
2012/12/15
949
1
sicily 1150,1151

// Problem#: 1151// Submission#: 2982372// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License// URI: http://creativecom......

猜猜我是吧
2014/10/12
95
0

没有更多内容

加载失败,请刷新页面

加载更多

zk中ToBeAppliedRequestProcessor解析

ToBeAppliedRequestProcessor在Leader中 在已处理事务和最后处理事务处理器之间,处理器链上下一个是FinalRequestProcessor public void processRequest(Request request) throws RequestPro...

writeademo
33分钟前
3
0
Allegro快捷键设置-PCB环境

立题简介: 内容:简单介绍Allegro绘制的PCB环境下的快捷键; 来源:实际使用得出; 作用:对Allegro绘制PCB快捷键进行介绍; PCB环境:Cadence 16.6; 立题详解: 对“allegro”板而言,其在...

demyar
34分钟前
3
0
idea maven web项目启动build时报错java.lang.NullPointerException

之前还好好的,重启一下idea就报这个错了,大概率是tomcat没杀掉端口被占用了,在tomcat配置中更换一下sever端口就好了

宇辰OSC
38分钟前
3
0
weed3-2.3.1.查询之输出

Weed3 一个超轻量级ORM框架(只有0.1Mb哦) 源码:https://github.com/noear/weed3 源码:https://gitee.com/noear/weed3 查询可是个复杂的话题了,可能我们80%的数据库处理都在查询。 今天先...

刘之西东
38分钟前
3
0
【Android JetPack系列】数据绑定:DataBinding

参考MVVM

Agnes2017
47分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部