ACM->dijkstra+heap+stlひとり旅hdu 2066
5452 ワード
一人旅
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15164 Accepted Submission(s): 5155
Problem Description
草児は方向音痴(杭電に1年以上いたのに、キャンパスで道に迷った人、汗~)でしたが、草児は旅行が大好きで、旅の途中でたくさんの人に会えるので(白馬王子、^0^)ああ、いろいろなことがあって、自分の経験を豊かにすることができて、また美しい景色を见ることができます......草は多くの地方に行きたいです.彼女は东京タワーに行って夜景を见に行きたいです.ベネチアに行って映画を见に行きます.阳明山に行って芋を见に行きます.ニューヨークに行って雪の景色を见に行きます.パリに行ってコーヒーを饮んで手纸を书きます.北京に行って孟姜女を见舞いに行きます.冬休みが近づいています.ちゃんと休みを取ってあげなきゃいけないんだけど、訓練をおろそかにしちゃいけないんだから、草は一番短い時間で行きたいところに行くことにしたんだよ.草の家は小さな町にあって列車が通っていないから、隣の町に行って列車に乗るしかないんだよ(かわいそう~).
Input
入力データには複数のグループがあり、各グループの最初の行は3つの整数T、S、Dであり、T本の道があり、草の家と隣接する都市にはS個、草の行きたい場所にはD個があることを示している.
次にT行があり、各行に3つの整数a,b,timeがあり、a,b都市間の車の距離がtime時間であることを示す.(1=続くT+1行目にはS個の数があり、草家とつながっている都市を表す.
次のT+2行目にD個の数があり、草が地方に行きたいことを表す.
Output
草を出してある好きな都市に行ける最短時間.
Sample Input
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15164 Accepted Submission(s): 5155
Problem Description
草児は方向音痴(杭電に1年以上いたのに、キャンパスで道に迷った人、汗~)でしたが、草児は旅行が大好きで、旅の途中でたくさんの人に会えるので(白馬王子、^0^)ああ、いろいろなことがあって、自分の経験を豊かにすることができて、また美しい景色を见ることができます......草は多くの地方に行きたいです.彼女は东京タワーに行って夜景を见に行きたいです.ベネチアに行って映画を见に行きます.阳明山に行って芋を见に行きます.ニューヨークに行って雪の景色を见に行きます.パリに行ってコーヒーを饮んで手纸を书きます.北京に行って孟姜女を见舞いに行きます.冬休みが近づいています.ちゃんと休みを取ってあげなきゃいけないんだけど、訓練をおろそかにしちゃいけないんだから、草は一番短い時間で行きたいところに行くことにしたんだよ.草の家は小さな町にあって列車が通っていないから、隣の町に行って列車に乗るしかないんだよ(かわいそう~).
Input
入力データには複数のグループがあり、各グループの最初の行は3つの整数T、S、Dであり、T本の道があり、草の家と隣接する都市にはS個、草の行きたい場所にはD個があることを示している.
次にT行があり、各行に3つの整数a,b,timeがあり、a,b都市間の車の距離がtime時間であることを示す.(1=続く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
Author
Grass
普通做法:
不额外加边
0MS | 372K | 2188 B |
Problem : 2066 ( ) Judge Status : Accepted
RunId : 9513473 Language : C++ Author : 455707843
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int INF = ~0U >> 1;
const int MAXN = 1000 + 10;
struct Edge
{
int v, w, next;
}edge[MAXN * MAXN + 10];
int temp[MAXN], des[MAXN];
int head[MAXN], e;
int dis[MAXN];
bool vis[MAXN];
int t, s, d;
priority_queue > q;
void add(int u, int v, int w)
{
edge[e].v = v;
edge[e].w = w;
edge[e].next = head[u];
head[u] = e++;
edge[e].v = u;
edge[e].w = w;
edge[e].next = head[v];
head[v] = e++;
}
void init()
{
e++;
memset(head, -1, sizeof(head));
}
int dijkstra(int x)
{
memset(vis, false, sizeof(vis));
for (int i = 0; i < MAXN; i++)
{
dis[i] = INF;
}
dis[x] = 0;
q.push(make_pair(0, x));
while (!q.empty())
{
int cur = q.top().second;
q.pop();
if (!vis[cur])
{
vis[cur] = true;
for (int i = head[cur]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if (!vis[v] && dis[v] > dis[cur] + edge[i].w)
{
dis[v] = dis[cur] + edge[i].w;
q.push(make_pair(-dis[v], v));
}
}
}
}
int mi = INF;
for (int i = 0; i < d; i++)
{
mi = min(mi, dis[des[i]]);
}
return mi;
}
void solve()
{
int mi = INF;
for (int i = 0; i < s; i++)
{
mi = min(mi, dijkstra(temp[i]));
}
cout << mi << endl;
}
void input()
{
int u, v, w;
while (cin >> t >> s >> d)
{
init();
for (int i = 0; i < t; i++)
{
cin >> u >> v >> w;
add(u, v, w);
}
for (int i = 0; i < s; i++)
{
cin >> temp[i];
}
for (int i = 0; i < d; i++)
{
cin >> des[i];
}
solve();
}
}
int main()
{
input();
return 0;
}