hdu 2066 한 사람의 여행 최적화 플 로 이 드 알고리즘 해결
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21056 Accepted Submission(s): 7335
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
9
好忧桑的，，我感觉我明明比discuss里的代码优化多了，，可还是比他耗时多o(╯□╰)o
我wrong了N次，，很难想象，，这么简单的一题。。。。。哎，为了熟悉floyd，真的是拼了。
最起码我明白，，不能用floyd求单源最短路径。。是我自己异想天开了，，也是我没真正弄明白Floyd算法的DP的含义。
还是很有收获的，不过以后刷题，，可能会很少用Floyd了吧。。毕竟O(n^3)的复杂度。。稍微复杂一点的题，，都是超时的命。
代码：
#include
#include
#define MAX 1050
#define INF 500000000
int dp[MAX][MAX] ;
bool like[MAX] ;
bool temp[MAX] ;
int min(int a ,int b)
{
return a>b?b:a ;
}
int main()
{
int t,s,d;
while(scanf("%d%d%d",&t,&s,&d) != EOF)
{
memset(temp,false,sizeof(temp)) ;
memset(like,false,sizeof(like)) ;
for(int i = 0 ; i < MAX ; ++i)
{
for(int j = 0 ; j <= i ; ++j)
{
dp[i][j] = INF ;
dp[j][i] = INF ;
}
}
int count = 0 ;
for(int i = 0 ; i < t ; ++i)
{
int x , y , w;
scanf("%d%d%d",&x,&y,&w) ;
if(wcount||y>count)
{
count = x>y?x:y ;
}
}
int ans = INF ;
for(int i = 0 ; i < s ; ++i)
{
int index ;
scanf("%d",&index) ;
temp[index] = true ;
}
for(int i = 0 ; i < d ; ++i)
{
int index ;
scanf("%d",&index) ;
like[index] = true ;
}
for(int k = 1 ; k <= count ; ++k)
{
for(int i = 1 ; i <= count ; ++i)
{
if(dp[i][k] == INF)
{
continue ;
}
for(int j = 1 ; j <= count ; ++j)
{
if(dp[i][j]>dp[i][k]+dp[k][j])
{
dp[i][j] = dp[i][k]+dp[k][j] ;
}
if(temp[i] && like[j])
{
ans = min(dp[i][j] , ans) ;
}
}
}
}
printf("%d
",ans) ;
}
return 0 ;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
