hdu 1596 find the safest road 최 단 로 FLoyd 알고리즘
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7892 Accepted Submission(s): 2798
Problem Description
XX 별 에는 많은 도시 가 있 습 니 다.도시 마다 하나 이상 의 비행 통로 가 있 습 니 다.그러나 모든 길이 안전 한 것 은 아 닙 니 다.모든 길 에는 안전 계수 s 가 있 습 니 다.s 는 0 과 1 칸 의 실수(0,1 포함)입 니 다.u 에서 v 까지 의 통로 P 의 안전 도 는 Safe(P)=s(e1)*s(e2)...*s(ek)e1,e2,ek 는 P 의 가장자리 입 니 다.지금 8600 은 여행 을 가 고 싶 습 니 다.이렇게 많은 길 을 마주 하고 그 는 가장 안전 한 길 을 찾 으 려 고 한다.하지만 8600 은 수학 을 잘 못 해 요.도와 주 고 싶 어 요^ ^
Input
여러 개의 테스트 인 스 턴 스 를 포함 하여 입력 하 십시오.모든 인 스 턴 스 는 다음 을 포함 합 니 다.
첫 줄n 도시 의 개수 n<=1000;
이 어 n*n 의 행렬 은 두 도시 간 의 안전 계 수 를 나타 낸다.(0 은 그 두 도시 사이 에 직접적인 통로 가 없다 고 이해 할 수 있다)
이 어 8600 개 여행 코스 Q 개 로 줄 당 두 개의 숫자 가 있 으 며 8600 이 있 는 도시 와 가 야 할 도 시 를 나타 낸다.
Output
86 이 그의 목적지 에 도달 하지 못 하면"What a pity!"를 출력 합 니 다.
다른 수출 두 도시 간 의 가장 안전 한 도로 의 안전 계 수 는 세 개의 소 수 를 유지한다.
Sample Input
3
1 0.5 0.5
0.5 1 0.4
0.5 0.4 1
3
1 2
2 3
1 3
Sample Output
0.500
0.400
0.500
물이 지나 가면 할 말 이 없다.
코드:
#include <stdio.h>
#define MAX 1010
double dp[MAX][MAX] ;
double max(double a , double b)
{
return a>b?a:b ;
}
void floyd(int n)
{
for(int k = 1 ; k <= n ; ++k)
{
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
{
dp[i][j] = max(dp[i][j],dp[i][k]*dp[k][j]) ;
}
}
}
}
int main()
{
int n ;
while(~scanf("%d",&n))
{
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
{
scanf("%lf",&dp[i][j]) ;
}
}
int m ;
floyd(n) ;
scanf("%d",&m) ;
for(int i = 0 ; i < m ; ++i)
{
int x , y;
scanf("%d%d",&x,&y) ;
if(dp[x][y] == 0)
{
puts("What a pity!") ;
}
else
{
printf("%.3lf
",dp[x][y]) ;
}
}
}
return 0 ;
}
그대 와 함께 격려 하 다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준(baekjoon)-C++ 정리1181 단어 정렬 벡터(vector) v.begin():벡터 시작점의 주소 값 반환 v.end(): 벡터 (끝부분+1) 주소 값 반환 v.push_back():벡터의 마지막 부분에 새로운 요소를 추가함 find(f...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
