首页 > 其他 > 详细

Light OJ - 1002 - Country Roads 题解

时间:2014-04-21 04:03:11      阅读:634      评论:0      收藏:0      [点我收藏+]

不是很难的题目,却搞得我好头痛,这里是应该了变形的Dijstra算法了,因为这里求最短路径不是把所有路径相加,而是把路径上所有的值取最大值,这个最大值越小,就说明结果最优,也不管你绕了多长的路。

另外值得注意的就是memset这个函数,看来很多人栽跟斗啊,这个函数只能用来清零,是不能用来初始化值的,因为它是按照字符来初始化值的,所以计算好也可以给整形清零,但是这次我用来给bool数组清零,结果出现奇怪的现象。还是使用fill这个函数或者是循环赋值吧,不能偷懒的了。

下面是题目:

I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

bubuko.com,布布扣

For example, in the above picture, if we want to go from 0 to 4, then we can choose

1)      0 - 1 - 4 which costs 8, as 8 (1 - 4) is the maximum road we used

2)      0 - 2 - 4 which costs 9, as 9 (0 - 2) is the maximum road we used

3)      0 - 3 - 4 which costs 7, as 7 (3 - 4) is the maximum road we used

So, our result is 7, as we can use 0 - 3 - 4.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000) indicating that there is a road between u and v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.

Output

For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print ‘Impossible‘.

Sample Input

Output for Sample Input

2

 

5 6

0 1 5

0 1 4

2 1 3

3 0 7

3 4 6

3 1 8

1

 

5 4

0 1 5

0 1 4

2 1 3

3 4 7

1

Case 1:

4

0

3

7

7

Case 2:

4

0

3

Impossible

Impossible


题目还是挺有意思的,变形的Dijstra,学好这个算法还是很有必要的。
标准的Dijstra参考资料:
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/


#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <assert.h>

using namespace std;

const static int MAX_COST = 20001;

int minDist(vector<int> &rs, bool *splitSet)
{
	int min_val = MAX_COST, id = -1;
	for (unsigned i = 0; i < rs.size(); i++)
	{
		if (!splitSet[i] && rs[i] < min_val)
		{
			min_val = rs[i];
			id = i;
		}
	}
	return id;
}

vector<int> findPaths(vector<vector<int> > &graph, const int sp)
{
	vector<int> rs(graph.size(), MAX_COST);
	bool *splitSet = new bool[graph.size()];
	for (unsigned i = 0; i < graph.size(); i++)
	{
		splitSet[i] = false;
	}
	rs[sp] = 0;

	for (unsigned i = 0; i < graph.size(); i++)
	{
		int id = minDist(rs, splitSet);
		if (-1 == id)break;//之后的都没路了

		splitSet[id] = true;
		for (unsigned j = 0; j < graph.size(); j++)
		{
			if (!splitSet[j] && -1 != graph[id][j])
			{
				int tmp = max(rs[id], graph[id][j]);
				rs[j] = min(rs[j], tmp);
			}
		}
	}
	delete [] splitSet;
	return rs;
}

void CountryRoads()
{
	int T = 0, n = 0, m = 0, u = 0, v = 0, w = 0, t = 0;
	cin>>T;
	for (int i = 0; i < T; i++)
	{
		cin>>n>>m;		
		vector<vector<int> > graph(n, vector<int>(n, -1));
		for (int j = 0; j < m; j++)
		{
			cin>>u>>v>>w;
			assert(0<=u && u<n && 0<=v && v<n);
			if (-1 == graph[u][v]) graph[u][v] = graph[v][u] = w;
			else graph[u][v] = graph[v][u] = min(graph[u][v], w);
		}
		cin>>t;
		vector<int> rs = findPaths(graph, t);
		cout<<"Case "<<i+1<<":"<<endl;
		for (unsigned i = 0; i < rs.size(); i++)
		{
			if (MAX_COST == rs[i]) cout<<"Impossible"<<endl;
			else cout<<rs[i]<<endl;
		}
	}
}
int main()
{
	CountryRoads();
	return 0;
}



Light OJ - 1002 - Country Roads 题解,布布扣,bubuko.com

Light OJ - 1002 - Country Roads 题解

原文:http://blog.csdn.net/kenden23/article/details/24191003

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!