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;
}