HDU 2066 dijkstra最短経路
C-一人旅
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
草は方向音痴だが(杭電に1年以上いたのに、キャンパスで道に迷った人、汗~)、草はまだ旅行が好きで、旅の途中でたくさんの人に会えるから(白馬の王子さま、^0^)、いろいろなことがあって、自分の経験を豊かにすることができて、また美しい景色を見ることができます......草は多くの地方に行きたいです.彼女は東京タワーに行って夜景を見に行きたいです.ベネチアに行って映画を見に行きます.陽明山に行って芋を見に行きます.ニューヨークに行って純粋に雪景色を見に行きます.パリに行ってコーヒーを飲んで手紙を書いて、北京に行って孟姜女を見舞いに行きます.冬休みが近づいています.ああ、無駄にしてはいけないよ.自分にちゃんと休暇を取らなければならないのに、訓練をおろそかにしてはいけないんだよ.だから、草は一番短い時間で自分の行きたいところに行くことにしたんだよ.草の家は小さな町で列車が通っていないので、隣の町に行って列車に乗るしかありません(かわいそうですね~).
Input
入力データには複数のグループがあり、各グループの最初の行は3つの整数T、S、Dであり、T本の道があり、草の家と隣接する都市にはS個、草の行きたい場所にはD個があることを示している.
次にT行があり、各行に3つの整数a,b,timeがあり、a,b都市間の車の距離がtime時間であることを示している.(1=<(a,b)<=1000;a,bの間には複数の道がある可能性がある)
続くT+1行目にはS個数があり、草児家とつながっている都市を表す.
次のT+2行目にD個の数があり、草が地方に行きたいことを表す.
Output
草を出してある好きな都市に行ける最短時間.
Sample Input
Sample Output
重いエッジがあります!
ACcode:
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
草は方向音痴だが(杭電に1年以上いたのに、キャンパスで道に迷った人、汗~)、草はまだ旅行が好きで、旅の途中でたくさんの人に会えるから(白馬の王子さま、^0^)、いろいろなことがあって、自分の経験を豊かにすることができて、また美しい景色を見ることができます......草は多くの地方に行きたいです.彼女は東京タワーに行って夜景を見に行きたいです.ベネチアに行って映画を見に行きます.陽明山に行って芋を見に行きます.ニューヨークに行って純粋に雪景色を見に行きます.パリに行ってコーヒーを飲んで手紙を書いて、北京に行って孟姜女を見舞いに行きます.冬休みが近づいています.ああ、無駄にしてはいけないよ.自分にちゃんと休暇を取らなければならないのに、訓練をおろそかにしてはいけないんだよ.だから、草は一番短い時間で自分の行きたいところに行くことにしたんだよ.草の家は小さな町で列車が通っていないので、隣の町に行って列車に乗るしかありません(かわいそうですね~).
Input
入力データには複数のグループがあり、各グループの最初の行は3つの整数T、S、Dであり、T本の道があり、草の家と隣接する都市にはS個、草の行きたい場所にはD個があることを示している.
次にT行があり、各行に3つの整数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
重いエッジがあります!
ACcode:
#pragma warning(disable:4786)//
#pragma comment(linker, "/STACK:102400000,102400000")//
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rds(x) scanf("%s",x)
#define rdc(x) scanf("%c",&x)
#define ll long long int
#define maxn 1111
#define mod 1000000007
#define INF 0x3f3f3f3f //int
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define MT(x,i) memset(x,i,sizeof(x))
#define PI acos(-1.0)
#define E exp(1)
using namespace std;
bool vis[maxn];
int pre[maxn],cost[maxn][maxn],lowcost[maxn],aa[maxn],bb[maxn];
void dijkstra(int n,int beg){
FOR(i,0,n){lowcost[i]=INF;vis[i]=false;pre[i]=-1;}
lowcost[beg]=0;
FOR(j,1,n){
int k=-1;int min=INF;
FOR(i,1,n)
if(!vis[i]&&lowcost[i]<min){
min=lowcost[i];
k=i;
}
if(k==-1)break;
vis[k]=true;
FOR(i,1,n)
if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i]){
lowcost[i]=lowcost[k]+cost[k][i];
pre[i]=k;
}
}
}
int t,s,d,a,b,c,ans,n;
int main(){
while(scanf("%d%d%d",&t,&s,&d)!=EOF){
MT(cost,INF);n=-INF;
FOR(i,1,t){
rd2(a,b);rd(c);
if(c<cost[a][b])
cost[a][b]=cost[b][a]=c;
n=max(max(a,b),n);
}
FOR(i,1,s)rd(aa[i]);
FOR(i,1,d)rd(bb[i]);
ans=INF;
FOR(i,1,s){
dijkstra(n,aa[i]);
FOR(i,1,d)ans=min(ans,lowcost[bb[i]]);
}
printf("%d
",ans);
}
return 0;
}
/*
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
*/