HDU - 1874 원활 한 공사 계속 [dijkstra 템 플 릿]

원활 한 공사 가 계속되다.
Time Limit: 3000/1000 MS ( Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 46054 Accepted Submission(s): 17145
Problem Description
모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 선택 할 수 있 고 어떤 방안 은 다른 방안 보다 걷 는 거리 가 훨씬 짧다.이것 은 행인 들 을 매우 곤란 하 게 한다.
지금 은 출발점 과 종점 을 알 고 있 습 니 다. 출발점 에서 종점 까지 가장 짧 은 거 리 를 걸 어야 하 는 지 계산 해 보 세 요.
Input
이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.
각 조 의 데이터 첫 줄 에는 두 개의 정수 N 과 M (0 다음은 M 행 도로 정보 가 포함 되 어 있 습 니 다. 각 줄 에는 세 개의 정수 A, B, X (0 < = A, B 가 다음 줄 에 두 개의 정수 S, T (0 < = S, T) 가 있 습 니 다.
Output
각 그룹의 데이터 에 대해 서 는 한 줄 에서 걸 어야 할 가장 짧 은 거 리 를 출력 하 십시오. S 에서 T 까지 의 경로 가 존재 하지 않 으 면 출력 - 1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
----------
1. 제목: 두 마을 의 가장 짧 은 거리 (길이 없 을 수 있 음) 를 구하 라. 2. 사고: 그림 을 인접 행렬 에 저장 한 다음 에 dijkstra 로 두 점 사이 의 가장 짧 은 거 리 를 구하 라. 두 점 사이 에 연결 되 지 않 으 면 거리 가 무한 하고 수출 할 때 판단 하면 된다. 3. 실수: dijkstra 의 3 단계 와 초기 화 를 명심 하 라. 4. 코드 는 다음 과 같다.

#include
#include
using namespace std;

#define inf 0xfffffff//28  
const int MAXN=1e3+10;
int map[MAXN][MAXN],dis[MAXN];
bool vis[MAXN];

void dijkstra(int n,int s)
{
memset(vis,false,sizeof(vis));
for(int i=0;idis[k]+map[k][j])
dis[j]=dis[k]+map[k][j];
}
}

}

int main()
{
int i,j,n,m,u,v,w,s,e;
while(~scanf("%d %d",&n,&m))
{
for(i=0;iw)
map[u][v]=map[v][u]=w;
}
scanf("%d %d",&s,&e);
dijkstra(n,s);
if(dis[e]==inf) printf("-1
");//           
else printf("%d
",dis[e]);
}
return 0;
}

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

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

여름방학 합숙 훈련 day 6 - 데이터 구조 실험의 창고 와 대열 3: 접미사 값 구하 기

이원 연산 자 를 기반 으로 한 접두사 표시 식 (기본 동작 수 는 모두 정수) 에 대해 대표 적 인 산술 표현 식 의 값 을 구하 십시오. 산술 식 의 접미사 문자열 을 입력 하고 '\ #' 을 끝 표지 로 합 니...

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

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

HDU - 1874 원활 한 공사 계속 [dijkstra 템 플 릿]

좋은 웹페이지 즐겨찾기