MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2066
题目描述:
一个人的旅行
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4077 Accepted Submission(s): 1348
Problem Description
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
Input
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。
Output
输出草儿能去某个喜欢的城市的最短时间。
Sample Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
Sample Output
9
题目分析:
刚开始做的时候也没做分析, 直接就是枚举每个起点到每个终点的 最短距离, 然后取最短的路, 很显然, TLE.................
还是自己没有把DIJKSTRA 算法理解好.... 再次看了一遍算法的描述和数据结构书上的 sample后 发现, 其实算法执行过程中
已经把起点到其他点的最短距离全部算出来了, 所以只需要 枚举每个起点就可以了, 兴奋之下, 马上修改了代码, Submit! ......
很 杯具, 还是tle ...... 不明白为什么.....看网上其他人写的 解题报告 , 原来很多人也是这做的, 枚举起始点, 但是他们的却可以AC.
虽然时间一般是 100MS左右. 这里我一直很纠结, 不明白同样的算法为什么我的会TLE.
在 AMB 大牛的提示下, 不需要全部枚举, 只要把所有起点的距离都设置成0就可以了, 但是不知道为什么, 还是一直TLE.
最后的办法是: 设置一个起点指向所有起点, 之间的距离设置为 1, 同样 设置一个终点指向所有终点, 距离同样设置为1, 最后
使用 DIJKSTRA 算法 求出起点到终点的最短距离 - 2 就行了.
代码如下:
#include <iostream>
using namespace std;
const int INF = 0x7FFFFFFF;
int T,S,D,L;
const int MAXN=1005; //点个数
int graph[MAXN][MAXN];
int s[MAXN];
int d[MAXN];
int Dijkstra ( int beg, int end )
{
bool hash[MAXN];
int path[MAXN];
for ( int i = 0; i <= L; ++ i )
{
hash[i] = true;
path[i] = INF;
}
hash[beg] = false;
path[beg] = 0;
while ( beg != end )
{
for ( int i = 0; i <= L; ++ i )
{
if ( graph[beg][i] != 0 )
{
if ( path[i] > path[beg] + graph[beg][i] )
path[i] = path[beg] + graph[beg][i];
}
}
int min = INF;
for ( int i = 0; i <= L; ++ i )
{
if ( min > path[i] && hash[i] )
{
min = path[i];
beg = i;
}
}
hash[beg] = false;
}
return path[end];
}
int main ()
{
while ( scanf ( "%d%d%d",&T,&S,&D ) != EOF )
{
memset ( graph , 0 , sizeof ( graph ) );
L = 0;
for ( int i = 1; i <= T; ++ i )
{
int r,c,cost;
scanf ( "%d%d%d",&r,&c,&cost );
if ( graph[r][c] == 0 )
graph[r][c] = graph[c][r] = cost ;
else
{
if ( cost < graph[r][c] )
graph[r][c] = graph[c][r] = cost ;
}
if ( L < max ( r,c ) )
L = max ( r,c );
}
for ( int i = 0; i != S; ++ i )
{
scanf ( "%d",&s[i] );
graph[0][ s[i] ] = 1;
graph[ s[i] ][0] = 1;
}
L ++;
for ( int i = 0; i != D; ++ i )
{
scanf ( "%d",&d[i] );
graph[ d[i] ][ L ] = 1;
graph[ L ][ d[i] ] = 1;
}
cout << Dijkstra ( 0,L ) - 2 << endl;
}
return 0;
}
顺便 0rz 下大牛 代码:
#include <iostream>
#define MAX 1005
#define INF 0x7FFF
#define CMP(A,B) (A.d < B.d)
using namespace std;
int d[MAX][MAX];
class HNode {
public:
int v;
int d;
};
class Heap {
public:
HNode h[MAX * 2];
int n, p, c;
Heap() {
n = 0;
}
void inline ins(HNode e) {
for (p = ++n; p > 1 && CMP(e,h[p>>1]); h[p] = h[p>>1], p >>= 1)
;
h[p] = e;
}
int inline pop(HNode &e) {
if (!n)
return 0;
for (e = h[p = 1], c = 2; c < n
&& CMP(h[c += (CMP(h[c + 1],h[c]) && c < n - 1)], h[n]);
h[p] = h[c], p = c, c <<= 1)
;
h[p] = h[n--];
return 1;
}
};
int Dijkstra(int A, int B, int N) {
int dist[MAX];
int mask[MAX];
int Tmp;
Heap h;
HNode e, ne;
for (int i = 0; i < N; i++) {
dist[i] = INF;
mask[i] = 0;
}
dist[e.v = A] = (e.d = 0);
h.ins(e);
while (h.pop(e)) {
if (!mask[e.v]) {
mask[e.v] = 1;
for (int i = 0; i < N; i++) {
if (!mask[i] && (Tmp = e.d + d[e.v][i])
< dist[i]) {
dist[ne.v = i] = (ne.d = Tmp);
h.ins(ne);
}
}
}
}
return dist[B];
}
int main() {
int T, S, D, M;
int st, en, tm;
while (scanf("%d %d %d", &T, &S, &D)!=EOF) {
M = 0;
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
d[i][j] = INF;
for (int i = 0; i < T; i++) {
scanf("%d %d %d", &st, &en, &tm);
if (tm < d[st][en]) {
d[st][en] = d[en][st] = tm;
}
M = st> M ? st : M;
M = en> M ? en : M;
}
M = M + 1;
for (int i = 0; i < S; i++) {
scanf("%d", &st);
d[0][st] = 1;
d[st][0] = 1;
}
for (int i = 0; i < D; i++) {
scanf("%d", &en);
d[M][en] = 1;
d[en][M] = 1;
}
cout<<Dijkstra(0, M, M+1)-2<<endl;
}
return 0;
}