HDU 2066 혼자 만 의 여행.

혼자 만 의 여행
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 33498 Accepted Submission(s): 11513
Problem Description
초 아 는 길 치 였 지만(항 저 우 전기 에서 1 년 넘 게 있 었 는데 도 캠퍼스 에서 길 을 잃 은 사람,땀~)여행 을 즐 겼 습 니 다.여행 중 에 많은 사람들 을 만 날 수 있 었 기 때 문 입 니 다(백마 탄 왕자,^0^).많은 일 들 이 있 었 고 자신의 경험 도 풍부 하고 아름 다운 풍경 도 볼 수 있 었 습 니 다...초 아 는 많은 곳 을 가 고 싶 었 습 니 다.도 쿄 철탑 에 가서 야경 을 보고 싶 었 습 니 다.베니스 에 가서 영 화 를 보고,양 명산 에 가서 토란 을 보고,뉴욕 에 가서 순 전 히 설경 을 보고,파리 에 가서 커피 를 마시고,편 지 를 쓰 고,북경 에 가서 맹 강 녀 를 방문 하고........................................그래서 풀 은 가장 짧 은 시간 에 자신 이 가 고 싶 은 곳 으로 가기 로 했다!풀 의 집 은 작은 마을 에 있어 기차 가 지나 가지 않 아 인근 도시 로 가서 기 차 를 탈 수 밖 에 없 었 다.

Input
입력 데 이 터 는 여러 그룹 이 있 습 니 다.각 그룹의 첫 줄 은 세 개의 정수 T,S 와 D 입 니 다.T 개의 길이 있 고 초아 집 과 인접 한 도 시 는 S 개 이 며 초아 가 가 고 싶 은 곳 은 D 개 입 니 다.
이 어 T 줄 이 있 고 줄 마다 세 개의 정수 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

Author

Grass

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=2066

这个题目其实从本质上来讲就是一个裸的最短路，不过有一个小小的变化就是要看出来可以把多个起点变成一个，及草儿的家，然后将他家到相邻城市的距离看做零就好。然后就在各个终点中选择最短的。。。。。。

告自己：一定要注意边界，否则就是wa;

代码如下：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxx=1111;
const int INF=INT_MAX/10;
int d[maxx]={0};
int t,s,dd;
int cun[maxx][maxx];
struct My{
int to,value;
My(int a,int b){
to=a;value=b;
}
};

vector<My>G[maxx];
typedef pair<int,int>p;
void add_edge(int from,int to,int value){
G[from].push_back(My(to,value));
}

void dijstra(int s){
    for(int i=0;i<maxx;i++)
    d[i]=INF;d[s]=0;
priority_queue<p,vector<p>,greater<p> >pqu;
pqu.push(p(0,s));
while(!pqu.empty())
{
    p pp=pqu.top();pqu.pop();
int v=pp.second;
if(d[v]<pp.first)continue;
for(int i=0;i<G[v].size();i++){
        My m=G[v][i];
if(d[m.to]>d[v]+m.value){d[m.to]=d[v]+m.value;pqu.push(p(d[m.to],m.to));}

}
}
}
void init(){
for(int i=0;i<maxx;i++)
G[i].clear();//maxx    
}


int main()
{
while(cin>>t>>s>>dd)
{
    init();  int a,b,c;
    memset(cun,0,sizeof(cun));
     for(int i = 0; i<1111; i++)
        {
            for(int j = 0; j<1111; j++)
                cun[i][j] = INF;
            cun[i][i] = 0;
        }
    for(int i=0;i<t;i++)
    {
            cin>>a>>b>>c;
      if(c<cun[a][b])cun[a][b]=cun[b][a]=c;
    }
 for(int i=0;i<maxx;i++)
 {
     for(int j=0;j<maxx;j++)
     {
         if(cun[i][j]!=0){add_edge(i,j,cun[i][j]);}
     }
 }
for(int i=0;i<s;i++){cin>>a;add_edge(0,a,1);add_edge(a,0,1);}
 int aa=INF;
 dijstra(0);
for(int i=0;i<dd;i++){cin>>a;aa=min(aa,d[a]);}
cout<<aa-1<<endl;
}
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

hdu 1233 또는 원활 한 공정 최소 생 성 트 리 (prim 알고리즘 + kruskal 알고리즘)

그럼 이 연결 서브 맵 은 G 의 최소 생 성 트 리 입 니 다.최소 생 성 트 리 를 구 하 는 흔 한 알고리즘 은 Prim 알고리즘 입 니 다. 욕심 전략 을 사용 하기 때문에 집합 S 에 새로운 정점 을 추가 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 2066 혼자 만 의 여행.

좋은 웹페이지 즐겨찾기