不是很难的题目，却搞得我好头痛，这里是应该了变形的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.
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 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.
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 |
#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